====== 조합의 합의 합 ======

===== 풀이 =====
  * $ \sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}} $ ([[ps:tutorial:이항계수#관련 공식과 정리들|반데르몽드 항등식]]) 을 적용하면, 문제는 C(6,3) + C(8,4) + C(10,5) + ... + C(2M, M) 을 구하는 것으로 단순화된다
  * 팩토리얼과 그것들의 모듈러 역원들을 전처리해두면 C(n,k)를 O(1)에 구할수 있으므로, 위의 식도 O(M)에 구할수 있다.
  * C(2n,n)을 C(2n-2,n-1) * (2n-1)(2n)/(n^2) 으로 이전 항을 이용해서 계산한다면 다른 전처리작업 없이 O(M)에 구하는 것도 가능하다. 이쪽이 더 빠르게 동작한다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 25823. 조합의 합의 합".

- Problem link: https://www.acmicpc.net/problem/25823
- Solution link: http://www.teferi.net/ps/problems/boj/25823

Tags: [math]
"""

MOD = 10**9 + 7


def main():
    M = int(input())

    answer = 0
    comb_2n_n = 6
    for i in range(3, M + 1):
        comb_2n_n = comb_2n_n * (i + i) * (i + i - 1) * pow(i, -2, MOD) % MOD
        answer += comb_2n_n

    print(answer % MOD)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_1}}