Codeforces Beta Round #53 C. Array

Array

_2nC_n-n。
小さいnに対して実際に調べて、OEISに訊いた。
理由を考えてみる。n個の数字からn個を選ぶ重複組合せは_2n-1C_n通り。選んだ数字を昇順と降順に並べることでbeautiful arrayが得られる。2_2n-1C_n=_2nC_n通り。ただし、これは全てが同じ数字の数列を2度数えている。そのような数列はn通り。
Mを法としたときの1/xはx^M-2。多倍長整数のまま計算するとTLEだった。

M = 1000000007
n = input()
ans = 1
for i in range(1,n+1):
    ans = ans * (n+i) * pow(i,M-2,M) % M
print (ans-n)%M