시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.515 초 1515 MB 236 168 140 74.074%

문제

욱제는 15라는 수를 굉장히 싫어한다. 그래서 0으로 시작하지 않고 1과 5로만 구성된 $N$자리 양의 정수 중에서, 15의 배수가 몇 개인지 궁금해졌다.

참가자 여러분도 궁금하지요?

안 궁금함? 15ㄱ

입력

$N$이 주어진다.

출력

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

제한

$1 \le N \le 1\,515$

예제 입력 1

1

예제 출력 1

0

예제 입력 2

2

예제 출력 2

1

예제 입력 3

3

예제 출력 3

1

예제 입력 4

1515

예제 출력 4

939178250