양의 정수 MMM이 주어질 때 다음 식의 값을 구하는 프로그램을 작성하시오.
∑_n=3M∑_k=0n(nk)2\displaystyle\sum\_{n=3}^M \sum\_{k=0}^n {n \choose k}^2∑_n=3M∑_k=0n(kn)2
이때 (nk){n \choose k}(kn)는 이항계수를 의미한다.
단, 답이 너무 커질 수 있으니 109+710^9 + 7109+7로 나눈 나머지를 출력한다.
첫째 줄에 정수 MMM이 주어진다. (3≤M≤200,0003 \le M \le 200\\,0003≤M≤200,000)
첫째 줄에 문제에서 주어진 식의 값을 109+710^9+7109+7로 나눈 나머지를 출력한다.
cho.sh