NUMTSN - 369 Numbers
7. 369 numbers
A number is said to be a 369 number if
- The count of 3s is equal to count of 6s and the count of 6s is equal to count of 9s.
- The count of 3s is at least 1.
For Example 12369, 383676989, 396 all are 369 numbers whereas 213, 342143, 111 are not.
Given A and B find how many 369 numbers are there in the interval [A, B]. Print the answer modulo 1000000007.
Input
The first line contains the number of test cases (T) followed by T lines each containing 2 integers A and B.
Output
For each test case output the number of 369 numbers between A and B inclusive.
Constraints
T<=100
1<=A<=B<=10^50
Sample Input
3
121 4325
432 4356
4234 4325667
Sample Output
60
58
207159
hide comments
|
freak2:
2020-11-20 07:46:41
even dp[51][17][17][2][2] giving tle Last edit: 2020-11-20 07:47:18 |
|
dangtiendung:
2020-11-11 10:47:56
Hoàng Anh Minh - 11 Tin - Chuyên Thái Bình trâu cũng AC Last edit: 2020-11-11 10:48:16 |
|
pranay_garg:
2019-10-10 14:50:51
How does it work if we initialize dp[] only once before test cases??
|
|
sahilshelangia:
2019-10-10 13:41:06
Last edit: 2019-10-10 13:41:31 |
|
zephyr_96:
2019-10-08 10:11:11
dp[51][55][55][55] gets TLE in java but AC in C++. |
|
quanpham0805:
2019-06-01 18:55:44
nhật hào bẩn
|
|
tranminhkhang7:
2019-05-22 10:47:50
Last edit: 2019-05-22 10:49:36 |
|
tototete:
2019-05-22 08:17:19
trâu cũng AC |
|
zingme123aptx:
2019-05-20 10:55:18
trâu cũng AC |
|
harshit2202:
2019-03-22 13:47:35
We should fill(dp,-1) in every test case. but this will give TLE.
|
Added by: | Saransh Bansal |
Date: | 2012-03-21 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |