問題文
どの目も出る確率が 61 のさいころを 1 つ用意し,次のように左から順に文字を書く。
さいころを投げ,出た目が 1,2,3 のときは文字列 AA を書き,4 のときは文字 B を,5 のときは文字 C を,6 のときは文字 D を書く。
さらに繰り返しさいころを投げ,同じ規則に従って,AA,B,C,D をすでにある文字列の右側につなげて書いていく。
たとえば,さいころを 5 回投げ,その出た目が順に 2,5,6,3,4 であったとすると,得られる文字列は,
AACDAAB
となる。このとき,左から 4 番目の文字は D,5 番目の文字は A である。
n を 2 以上の整数とする。n 回さいころを投げ,文字列を作るとき,文字列の左から n−1 番目の文字が A で,かつ n 番目の文字が B となる確率 (mod998244353) を求めよ。
注記
求める確率は必ず有理数となることが証明できます。
またこの問題の制約下では,その値を互いに素な 2 つの整数 P,Q を用いて QP と表したとき,R×Q≡P(mod998244353) かつ 0≤R<998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。
制約
- 2≤n≤2×105
入力
入力はすべて整数である。
出力
計算結果を一行に出力せよ。
サンプル
3 回さいころを投げたとき,左から 2 番目の文字が A で,かつ 3 番目の文字が B となるのは 1 回目で 1,2,3 のいずれかの目が出て,かつ 2 回目で 4 の目が出るときです。
このようになる確率は 121 です。