東大理系数学2015第2問(2)

どの目も出る確率が のさいころを つ用意し，次のように左から順に文字を書く。

さいころを投げ，出た目が のときは文字列 を書き， のときは文字 を， のときは文字 を， のときは文字 を書く。 さらに繰り返しさいころを投げ，同じ規則に従って， をすでにある文字列の右側につなげて書いていく。

たとえば，さいころを 回投げ，その出た目が順に であったとすると，得られる文字列は，

となる。このとき，左から 番目の文字は ， 番目の文字は である。

を 以上の整数とする。 回さいころを投げ，文字列を作るとき，文字列の左から 番目の文字が で，かつ 番目の文字が となる確率 を求めよ。

求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では，その値を互いに素な つの整数 を用いて と表したとき， かつ を満たす整数 がただ一つ存在することが証明できます。この を求めてください。

入力はすべて整数である。

n

計算結果を一行に出力せよ。

3

582309206

回さいころを投げたとき，左から 番目の文字が で，かつ 番目の文字が となるのは 回目で のいずれかの目が出て，かつ 回目で の目が出るときです。 このようになる確率は です。

114514

931132486