006 - すごろく IN 素数

問題文

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

入力

N P C

1≤N≤1000000000000000000=1018
0≤P≤300
0≤C≤300
P+C≥1

出力

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

入出力例

入力例１

1 1 1

出力例1

36

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

入力例2

1 2 0

出力例2

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

出力例3

41

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

入力例4

6 2 0

出力例4

61

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

入力例5

1 10 10

出力例5

9018009

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

入力例6

100000 8 12

出力例6

144097395