問題一覧 > 通常問題

No.3044 よくあるカエルさん

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 48
作問者 : Blue_S / テスター : Nauclhlt🪷 eiram naniwazu
0 ProblemId : 11836 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-26 18:28:46

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。