問題一覧 > 通常問題

No.1358 [Zelkova 2nd Tune *] 語るなら枚数を...

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 72
作問者 : KazunKazun / テスター : nok0nok0
6 ProblemId : 4459 / 出題時の順位表
問題文最終更新日: 2021-01-23 00:04:35

注意

yukicoder contest 279 (Zelkova and Cherry) の問題は 難易度順に並んではいない. よって, 問題文や難易度を表すの星の数, 正解者数等といった公開されている情報から問題を取捨選択することを強く推奨する.

問題文

Yuki君は3つのアイドルグループN道, K道, H道のCDを購入した.それぞれのグループのCDの値段は1枚につき $N$ 円, $K$ 円, $H$ 円であった. Yuki君はこの3つのアイドルグループのCDをそれぞれ何枚かずつ買い,その結果として合計 $Y$ 円になった. このとき,Yuki君が購入したCDの枚数の組み合わせとして可能な場合の数はいくつか?

ただし,解答は非常に大きくなる可能性があるので, $10^9+7$ で割った余りを出力せよ.

また,合計 $Y$ 円になるのであれば, 1枚も購入していないCDがあってもよいとする.

$T$ 個のテストケースについて答えよ.

制約

  • $1 \leq T \leq 20$
  • $1 \leq N,K,H\leq 10^6$
  • $1 \leq Y \leq 10^{12}$
  • $\min \left(\left \lfloor \dfrac{Y}{N} \right \rfloor, \left \lfloor \dfrac{Y}{K} \right \rfloor, \left \lfloor \dfrac{Y}{H} \right \rfloor \right) \leq 10^6$
  • 入力は全て整数である.

入力

入力は以下の形式で標準入力から与えられる. 入力の1行目は以下の通りである.
$T$
そして, 続く $T$ 行が $T$ 個のテストケースを表す. これらはそれぞれ以下の形式の行である.
$N\ K\ H\ Y$

出力

$T$ 行出力せよ. ただし, $i$ 行目には $i$ 番目のテストケースに対する答えを出力せよ. また, それぞれのテストケースについて, 最後に改行を忘れないこと.

サンプル

サンプル1
入力
4
2 3 5 9
4 5 1 1
10 10 10 1
31415 92653 58979 3238462643
出力
3
1
0
30554

[第1テストケースについて]
あり得る買い方は以下の3通りに限られる.

  • K道のCDを3枚買う.
  • N道のCDを2枚, H道のCDを1枚買う.
  • N道のCDを3枚, K道のCDを1枚買う.

[第2テストケースについて]
H道のCDを1枚だけ買う以外に方法がない.

[第3テストケースについて]
どうやっても不可能である.

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