No.215 素数サイコロと合成数サイコロ (3-Hard)
LayCurse問題文
素数サイコロとはそれぞれの面に \(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$ の方が良かったですけどね）
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。