No.215 素数サイコロと合成数サイコロ (3-Hard)

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 64 MB / タグ : / 解いたユーザー数 8
作問者 : LayCurseLayCurse

3 ProblemId : 444 / 出題時の順位表

問題文

素数サイコロとはそれぞれの面に \(2,3,5,7,11,13\) の整数が書かれているサイコロである。
合成数サイコロとはそれぞれの面に \(4,6,8,9,10,12\) の整数が書かれているサイコロである。
あるスゴロクでは、\(0\) のマスからスタートし、\(N\) のマスに辿り着いたらゴールである。
各ターン、\(P\) 個の素数サイコロと \(C\) 個の合成数サイコロを振り、出た目の和を \(x\) として、今いるマスが \(k\) ならば \(\min(k+x, N)\) のマスに移動する。
それぞれ素数サイコロと合成数サイコロは区別できないとして、ゴールする方法のパターン数を \({\rm mod}\ 1000000007\ (10^9+7)\) で求めるプログラムを書いて下さい。

入力

$N$ $P$ $C$

\(1 \leq N \leq 1000000000000000000 = 10^{18}\)
\(0 \leq P \leq 300\)
\(0 \leq C \leq 300\)
\(P + C \geq 1\)

出力

ゴールする方法パターン数 \({\rm mod}\ 1000000007\) を出力して下さい。
出力した後には改行して下さい。

サンプル

サンプル1
入力
1 1 1
出力
36

\(1\) ターンで必ずゴールできます。
素数サイコロがどの目が出るか、合成数サイコロがどの目が出るかで \(6 \times 6 = 36\) パターンあります。

サンプル2
入力
1 2 0
出力
21

サンプル1と同様に \(1\) ターンで必ずゴールできます。
しかし、素数サイコロは区別できないので、\(2\) つの素数サイコロの出目は \((2,2),(2,3),(2,5),(2,7),(2,11),(2,13),(3,3),(3,5),(3,7),(3,11),(3,13),(5,5),(5,7),(5,11),(5,13),(7,7),(7,11),(7,13),(11,11),(11,13),(13,13)\) の \(21\) パターンになります。

サンプル3
入力
5 2 0
出力
41

最初の出目が \((2,2)\) でない \(20\) 通りの場合は、\(1\) ターンでゴールできます。
最初の出目が \((2,2)\) であれば、もう \(1\) ターンかかり、\(2\) ターン目の出目は \(21\) パターンあります。

サンプル4
入力
6 2 0
出力
61

最初の出目が \((2,2), (2,3)\) でない \(19\) 通りの場合は、\(1\) ターンでゴールできます。
最初の出目が \((2,2), (2,3)\) であれば、もう \(1\) ターンかかり、\(2\) ターン目の出目はそれぞれ \(21\) パターンずつあります。

サンプル5
入力
1 10 10
出力
9018009

必ず \(1\) ターンでゴールできますが、サイコロの出目のパターンの数はそんなに小さくありません。

サンプル6
入力
100000 8 12
出力
144097395

ところで、問題IDが中々良い味出している気がしませんか?
($666$ の方が良かったですけどね)

提出ページヘ