Cho số n (1≤ n ≤ 10¹⁰⁰⁰⁰). Tìm số lượng số không âm nhỏ hơn n, có tổng bình phương các chữ số của nó chia hết cho 3.

Input:

Số n

Output:

Số lượng số tìm được. Chỉ ghi ra số dư của kết quả chia cho 10⁹+7.

Ví dụ