重複組み合わせ AtCoder Beginner Contest 021 D - 多重ループ

問題文

以下のリンクを参考に

http://abc021.contest.atcoder.jp/tasks/abc021_d

Note

重複組み合わせを求めればよい。 重複組み合わせについては以下のリンクを

重複組み合わせ

n個の数字から重複ありでkこの数字を選べば良いので

nHr = n+r-1Cn-1 

を解けば良い。コンビネーションは毎度のことながら、フェルマーの小定理使って逆元をつかう。