問題一覧 > 通常問題

No.117 組み合わせの数

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 246
作問者 : LayCurse
16 ProblemId : 184 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-09-07 17:30:49

問題文

1 以上 N 以下の N 個の整数の中から，相異なる K 個の整数を選ぶパターンの数を C(N,K) と書きます．
1 以上 N 以下の N 個の整数の中から，相異なる K 個の整数を選び，順番に並べるパターンの数を P(N,K) と書きます．
1 以上 N 以下の N 個の整数の中から，重複を許して K 個の整数を選ぶパターンの数を H(N,K) と書きます．
（具体例はサンプル1の説明に書いてあるので必要ならば参照せよ．）
クエリが T 個与えられ，各クエリでは C(N,K),P(N,K),H(N,K) のどれかが与えられるので，その値を mod 109+7 で求めるプログラムを書いて下さい．

入力

T
S1
S2
⋮
ST

1≤T≤105
Sk は C(N,K),P(N,K),H(N,K) のどれかの形をしており，N,K は 0≤N,K≤106 を満たす
入力に余分なスペースなどは含まれません．詳しい入力形式はサンプルを見てください

出力

各クエリに対して，その値 mod 109+7 を 1 行で出力して下さい．

サンプル

サンプル1
入力
5
C(4,2)
C(5,1)
P(3,2)
P(10,10)
H(3,2)
出力
6
5
6
3628800
6

条件を満たす組み合わせの数は：
1 番目のクエリにおいて，{1,2},{1,3},{1,4},{2,3},{2,4},{3,4} の 6 通り存在します．
2 番目のクエリにおいて，{1},{2},{3},{4},{5} の 5 通り存在します．
3 番目のクエリにおいて，(1,2),(1,3),(2,1),(2,3),(3,1),(3,2) の 6 通り存在します．
4 番目のクエリにおいて，1 から 10 までを並び替える方法の数と等しいので 10! 通り存在します．
5 番目のクエリにおいて，{1,1},{1,2},{1,3},{2,2},{2,3},{3,3} の 6 通り存在します．

サンプル2
入力
5
C(1,1000000)
C(0,0)
P(1000000,1000000)
P(1,10)
H(1,1000)
出力
0
1
641102369
0
1

1 番目のクエリにおいて，106 個の異なる整数を選ぶことは不可能なので，答えは 0 です．
2 番目のクエリにおいて，0 個の整数を選ぶ方法の数は，何も選ばないという 1 通りです．
3 番目のクエリにおいて，答えは mod 109+7 で出力することを忘れないで下さい．

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