Cho số \(n\). Hãy tìm số lượng số có tổng bình phương các chữ số chia hết cho \(3\) nhỏ hơn \(n\). (Kết quả mod \(10^9+7\))

Input

• Số nguyên dương \(n\)

Output

• Số lượng số tìm được (Kết quả mod \(10^9+7\))

Điều kiện

• \(1 \le n \le 10^{10000}\)

Sample Input 1

9

Sample Output 1

3

Sample Input 2

10

Sample Output 2

4