No.215 Prime Dice and Composite Dice (3-Hard)

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.215 Prime Dice and Composite Dice (3-Hard)

レベル : / AI推定難易度 : 2900 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 64 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 32
作問者 :

LayCurse

お気に入りにしたユーザー ProblemId : 444 / 自分の提出

問題文最終更新日: 2026-06-25 06:42:02

This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

yukicoder contest 105 (順位表) の他の問題:

Problem Statement

A prime die is a die whose faces have the integers $2,3,5,7,11,13$ written on them.
A composite die is a die whose faces have the integers $4,6,8,9,10,12$ written on them.
In a certain sugoroku game, you start from square $0$, and you reach the goal upon arriving at square $N$.
Each turn, you roll $P$ prime dice and $C$ composite dice. Letting $x$ be the sum of the rolled values, if you are currently on square $k$, you move to square $\min(k+x, N)$.
Assuming that prime dice are indistinguishable from each other and composite dice are indistinguishable from each other, write a program that computes the number of patterns of ways to reach the goal, ${\rm mod}\ 1000000007\ (10^9+7)$.

Input

$N$ $P$ $C$

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

Output

Output the number of patterns of ways to reach the goal, ${\rm mod}\ 1000000007$.
Print a newline after the output.

Sample

Sample 1

Input

1 1 1

Output

You can always reach the goal in $1$ turn.
Depending on which value the prime die shows and which value the composite die shows, there are $6 \times 6 = 36$ patterns.

Sample 2

Input

1 2 0

Output

As in Sample 1, you can always reach the goal in $1$ turn.
However, since prime dice are indistinguishable, the rolls of the $2$ prime dice form the $21$ patterns $(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)$.

Sample 3

Input

5 2 0

Output

In the $20$ cases where the first roll is not $(2,2)$, you can reach the goal in $1$ turn.
If the first roll is $(2,2)$, it takes $1$ more turn, and there are $21$ patterns for the roll on turn $2$.

Sample 4

Input

6 2 0

Output

In the $19$ cases where the first roll is not one of $(2,2), (2,3)$, you can reach the goal in $1$ turn.
If the first roll is one of $(2,2), (2,3)$, it takes $1$ more turn, and there are $21$ patterns each for the roll on turn $2$.

Sample 5

Input

1 10 10

Output

You can always reach the goal in $1$ turn, but the number of patterns of dice rolls is not that small.

Sample 6

Input

100000 8 12

Output

144097395

By the way, don't you think this problem ID has quite a nice flavor to it?
(Though $666$ would have been better.)

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。