using System;
using System.Numerics;
using System.Linq;
using System.Collections.Generic;
using System.Text;
namespace Atcoder20200419
{
class ProgramA
{
static void Main(string args)
{
//入力
string s = Console.ReadLine();
string t = Console.ReadLine();
//sの文字数分それぞれ文字列が一致するか確認
for (int i = 0; i < s.Length; i++)
{
//もしダメならNoで出力
if (s[i] != t[i])
{
Console.WriteLine("No");
return;
}
}
//何も問題ないならyes
Console.WriteLine("Yes");
}
}
class ProgramB
{
static void Main(string args)
{
//入力
string s = Console.ReadLine().Split(' ');
long a = long.Parse(s[0]);
long b= long.Parse(s[1]);
long c = long.Parse(s[2]);
long k = long.Parse(s[3]);
//a>=kならk、それ以外でa+b>=kならa、それ以外はa-(k -a -b)になる
if(a >= k)
Console.WriteLine(k);
else if(a + b >= k)
Console.WriteLine(a);
else
Console.WriteLine(a - (k - a -b));
}
}
class ProgramC
{
static void Main(string args)
{
//入力
string s = Console.ReadLine().Split(' ');
int n = int.Parse(s[0]);
int m = int.Parse(s[1]);
int x = int.Parse(s[2]);
int[,] memo = new int[n, m + 1];
//理解度を記憶しておく関数
int rikai = new int[m];
//それぞれの値段と理解度を記録
for (int i = 0; i < n; i++)
{
string a = Console.ReadLine().Split(' ');
for (int j = 0; j < m + 1; j++)
memo[i, j] = int.Parse(a[j]);
}
//仮の答えを入れておく
int ans = 10000000;
//bit全探索
for(int i = 0; i < (1 << n);i++)
{
//カウント、フラグ、理解度をリセット
int count = 0;
int flag = 0;
for (int k = 0; k < m; k++)
rikai[k] = 0;
//その本がある場合は値段を足して、理解度も足す。
for (int j = 0; j < n; j++)
{
if ((i >> j & 1) == 1)
{
count += memo[j, 0];//値段を足す
for (int k = 0; k < m; k++)
rikai[k] += memo[j, k + 1];
}
}
//理解度判定（すべてx以上かどうか）
for (int k = 0; k < m; k++)
{
if (rikai[k] < x)
flag = 1;
}
//ぜんぶ理解度がx以上なら大小判定する（最小更新）
if (flag == 0)
ans = Math.Min(ans, count);
}
//もし一度も更新されないなら答えはないので-1。それ以外はそのまま。
if (ans == 10000000)
Console.WriteLine("-1");
else
Console.WriteLine(ans);
}
}
class ProgramD
{
static void Main(string args)
{
//入力
string s = Console.ReadLine().Split(' ');
int n = int.Parse(s[0]);
long k = long.Parse(s[1]);
string s2 = Console.ReadLine().Split(' ');
int a = new int[n];
int b = new int[n];//通ったかどうかを残す配列
int to = new int[n];//行き先を記録する配列
for (int i = 0; i < n; i++)
a[i] = int.Parse(s2[i]);
//場所1は最初かつ必ず通る
to[0] = 1;
b[0] = -1;
//初期設定
int townfrom = 1;
int townto = 0;
int count = 0;
//無限ループ（ワープのルートを探す）
while(true)
{
townto = a[townfrom - 1];//行き先を入れる
count++;//行き先を足す
if (b[townto - 1] == -1)
break;//もし行き先がすでにワープ済みなら終了
b[townto - 1] = -1;//そうでないならワープ済みにする
to[count] = townto;//ワープする場所として追加する
townfrom = townto;//次のワープのためtownfromにする
}
//どこにワープしたかを判定
int r = 0;
for(int i = 0; i < n;i++)
{
if (to[i] == townto)
r = i;//ワープした位置を記録
}
//もし一方通行のワープ回数以内ならその行き場を出す。循環内にあるなら、余りから判定
if(k <= r)
Console.WriteLine(to[k]);
else
Console.WriteLine(to[r + (k - r) % (count - r)]);
}
}
}
class ProgramE
{
static void Main(string args)
{
//入力
string s = Console.ReadLine().Split(' ');
long n = long.Parse(s[0]);
long m = long.Parse(s[1]);
long k = long.Parse(s[2]);
long MOD = 998244353;
//下準備
nCk com = new nCk();
com.fac = new long[n + 1];
com.inv = new long[n + 1];
com.finv = new long[n + 1];
com.mod = MOD;
com.max = n + 1;
//メモ作成
com.com_init();
long ans = 0;
//k回重複を許すのはm×n-kCk×(m-1)のn-k-1乗。よってその和をとる
for(long i = 0; i <= k;i++)
{
ans += (com.com(n - 1, i) * modpow(m - 1, n - i - 1, MOD)) % MOD; //変数はkじゃなくてiです！！
ans %= MOD;
}
//mは共通項なので最後にかけておく
ans *= m;
ans %= MOD;
//答え出力
Console.WriteLine(ans);
}
//繰り返し二乗法で求める
static long modpow(long a, long n, long MOD)
{
if (n == 0)
return 1;
if (n % 2 == 0)
{
long temp = modpow(a, n / 2, MOD);
return temp * temp % MOD;
}
return a * modpow(a, n - 1, MOD) % MOD;
}
}
//二項係数を求めるクラス
class nCk
{
public long mod;
public long max;
public long fac;
public long inv;
public long finv;
//メモ作成(前準備)
public void com_init()
{
fac[0] = 1;
fac[1] = 1;
finv[0] = 1;
finv[1] = 1;
inv[1] = 1;
for (long i = 2; i < max; i++)
{
fac[i] = i * fac[i - 1] % mod;
inv[i] = mod - inv[mod % i] * (mod / i) % mod;
finv[i] = finv[i - 1] * inv[i] % mod;
}
}
//二項計算
public long com(long n, long k)
{
if (n < 0 || k < 0)
return 0;
if (n < k)
return 0;
return fac[n] * (finv[n - k] * finv[k] % mod) % mod;
}
}
}
