조합의 합의 합

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

요약

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

문제

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

$\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$ 로 나눈 나머지를 출력한다.