No.3044 よくあるカエルさん
タグ : / 解いたユーザー数 48
作問者 :


問題文
$1$
の足場から
$10^{10000}$
の足場まで、合計
$10^{10000}$
個の足場があります。
カエルさんは同様に確からしい$6$面サイコロを振って、
$k$
未満の値が出た場合に1つ、
$k$
以上
$l$
未満の値が出た場合に2つ、
$l$
以上の値が出た場合に
$T$つ進みます。
$1$
の足場から出発して、サイコロを
$10^{100}$
回振って、出た目に沿って足場を進みました。
このとき、
$N$
の足場でちょうど立ち止まった確率
を求めてください。
答えの確率は有理数となることが証明できます。
このとき、答えを
$\frac{P}{Q}$
とすると、ある
$0 \le R \lt 998244353$
が一意に存在して
$QR \equiv P \mod 998244353$
となります。このときの
$R$
を出力してください。
入力
$N\ T$ $k\ l$
$1 \le N \le 10^9$
$2 \lt T \lt 100$
$1 \le k \le l \le 7$
出力
$ans$最後に改行してください。
サンプル
サンプル1
入力
3 5 4 6
出力
83187030
$1$を最初に$2$回出す、または$2$を最初に出す確率と等しいので、 $(3 / 6) ^ 2 + (2 / 6) = 7 / 12$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。