Sammaeining

Sammi가 가장 좋아하는 수는 $7$이다. 그는 그 수에 너무나 매료되어 있어서, 그가 하는 모든 일은 수 $7$을 중심으로 이루어진다. Sammi는 또한 Hackintosh 과자 애호가이기도 하다.

최근 Sammi는 과자 $n$개가 든 Hackintosh 과자 상자를 얻었다. 각 과자에는 $1$에서 $n$ 사이의 서로 다른 수가 하나씩 적혀 있었다. Sammi는 고른 모든 과자의 합이 $7$로 끝날 때, 그리고 그럴 때에만 그 과자들을 먹는다. Sammi는 먹을 수 있는 서로 다른 가능한 과자 조합이 몇 개인지 알고 싶어 한다.

채점

그룹 | 점수 | 제한 조건

1 | 20 | $1 \leq n \leq 20$

2 | 25 | $1 \leq n \leq 10^6$, $n$은 10의 배수이다

3 | 25 | $1 \leq n \leq 10^6$

4 | 15 | $1 \leq n \leq 10^{15}$, $n$은 10의 배수이다

5 | 15 | $1 \leq n \leq 10^{15}$

입력은 한 줄로 이루어지며, 상자의 크기를 나타내는 정수 $n$ ($1 \leq n \leq 10^9$)가 주어진다.

먹을 수 있는 서로 다른 가능한 과자 조합의 개수를 한 줄에 출력한다. 답이 매우 클 수 있으므로, 이를 $10^9+7$로 나눈 나머지를 출력해야 한다.