조합의 합의 합

시간 제한1초메모리 제한512 MB

요약

3부터 M까지의 각 n에 대해 이항계수 C(n,k)의 제곱을 k=0부터 n까지 더한 값을 모두 합쳐 10^9+7로 나눈 나머지를 구한다.

문제

양의 정수 $M$ 이 주어질 때 다음 식의 값을 구하는 프로그램을 작성하시오.

$\displaystyle\sum\_{n=3}^M \sum\_{k=0}^n {n \choose k}^2$

이때 ${n \choose k}$ 는 이항계수를 의미한다.

단, 답이 너무 커질 수 있으니 $10^9 + 7$ 로 나눈 나머지를 출력한다.

첫째 줄에 정수 $M$ 이 주어진다. ( $3 \le M \le 200\\,000$ )

첫째 줄에 문제에서 주어진 식의 값을 $10^9+7$ 로 나눈 나머지를 출력한다.