問題文

円周上に$2^m$個の点${\rm P}_0,{\rm P}_1,\cdots {\rm P}_{2^m-1}$が反時計回りに並んでおり、最初コマは点${\rm P}_0$に置かれています。この状態から、「$1$から$n$までの数字が全て等確率で出るサイコロを振り、出た目の数だけコマを反時計回りの点に移動させる」という操作を$k$回繰り返した後、コマが点${\rm P}_0$にある確率を${\rm mod}\ 998244353$で求めて下さい。

注意：求める確率が既約分数$p/q$で表されるとき、$rq≡p ({\rm mod}\ 998244353)$かつ $0≤r<998244353$を満たす整数$r$がこの問題の制約のもとで一意に定まります。この$r$が求める値です。

制約

• 入力は全て整数
• $1 \leq m \leq 20$
• $1 \leq n \leq 10^6$
• $1 \leq k \leq 10^{18}$

入力

入力は以下の形式で与えられます。

m n k

出力

結果を1行に出力して下さい。

サンプル

3 6 2

305019108

2回の移動によってコマが点${\rm P}_0$に移動するサイコロの出目の組み合わせは、$(2,6),(3,5),(4,4),(5,3),(6,2)$の5つなので、求める確率は$\frac{5}{6^2}=\frac{5}{36}$となります。$36r≡5 ({\rm mod}\ 998244353)$かつ$0≤r<998244353$を満たす整数$r$は$305019108$のみなので、答えは$305019108$となります。

6 6 3

0

この場合、どのような目が出ても3回の移動でコマが点${\rm P}_0$に移動することは無いため、求める確率は0です。

20 1000000 1000000000000000000

553051329

オーバーフローや制限時間に注意してください。