시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB132473536.842%

문제

진영이는 월드 카지노의 사장이다. 이번에 블랙잭의 신 최백준에게 거의 전 재산을 뺏기고 난 후에 어떻게 하면 다른 게임으로 돈을 되찾을까 고민하다가 새로운 주사위를 만들었다.

진영이가 만든 이 주사위는 6면이고, 각 면에는 양의 정수가 쓰여져 있고, 모두 다른 숫자들이다. 그리고, 주사위에 쓰여 있는 숫자의 평균은 M을 넘을 수 없다.

진영이가 원하는 주사위의 가능한 경우의 수를 구하는 프로그램을 작성하시오.

주사위 A와 B가 있을 때, B를 회전시켜서 A를 얻을 수 있다면, A와 B는 같은 주사위라고 한다. 정답이 매우 커질 수 있으니 1,000,000,007로 나눈 나머지를 출력한다.

입력

첫째 줄에 M이 주어진다. M은 1보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다.

출력

문제의 정답을 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

3

예제 출력 1

0

예제 입력 2

4

예제 출력 2

210

예제 입력 3

10

예제 출력 3

863010

예제 입력 4

50

예제 출력 4

375588112

힌트

가능한 가장 작은 주사위가 (1,2,3,4,5,6)인데, 이 주사위의 평균이 3.5이다. 따라서 3을 넘지 않는 주사위는 없다.

출처