問題一覧 > 通常問題

No.117 組み合わせの数

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 240
作問者 : LayCurseLayCurse
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)$ のどれかが与えられるので,その値を ${\rm mod}\ 10^9+7$ で求めるプログラムを書いて下さい.

入力

$T$
$S_1$
$S_2$
$\vdots$
$S_T$

$1 \leq T \leq 10^5$
$S_k$ は $C(N,K), P(N,K), H(N,K)$ のどれかの形をしており,$N,K$ は $0 \leq N,K \leq 10^6$ を満たす
入力に余分なスペースなどは含まれません.詳しい入力形式はサンプルを見てください

出力

各クエリに対して,その値 ${\rm mod}\ 10^9+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$ 番目のクエリにおいて,$10^6$ 個の異なる整数を選ぶことは不可能なので,答えは $0$ です.
$2$ 番目のクエリにおいて,$0$ 個の整数を選ぶ方法の数は,何も選ばないという $1$ 通りです.
$3$ 番目のクエリにおいて,答えは ${\rm mod}\ 10^9+7$ で出力することを忘れないで下さい.

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