Numbers Sum Squares Modulo ZERO
Xem PDF
Điểm:
1400 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho số \(n\) (\(1 \le n \le 10^{10000}\)). 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
- Một số nguyên dương \(n\).
Output
- In ra một số nguyên duy nhất là số lượng số tìm được sau khi chia lấy dư cho \(10^9+7\).
Constraints
- \(1 \le n \le 10^{10000}\)
Example
Test 1
Input
9Output
3Note
Các số thỏa mãn là: \(0, 3, 6\). (Tổng bình phương các chữ số lần lượt là \(0^2=0, 3^2=9, 6^2=36\), đều chia hết cho \(3\)).
Test 2
Input
10Output
4Note
Các số thỏa mãn là: \(0, 3, 6, 9\).
Test 3
Input
15Output
4Note
Các số thỏa mãn là: \(0, 3, 6, 9\). (Số \(12\) có \(1^2 + 2^2 = 5\) không chia hết cho \(3\)).
Bình luận