One day, Kirito found a electronic lock. He believed that there were something hidden behind that lock, so he thought he must break that lock to gain some information. After doing some research, he found that there was a secret string written on the lock { a sequence of digits like this:
1314151621391217481156718192010
Soon Kirito realized that it can be broke into pieces of distinct consecutive integers starting from one:
13, 14, 15, 16, 2, 1, 3, 9, 12, 17, 4, 8, 11, 5, 6, 7, 18, 19, 20, 10
"Maybe that is a hint to open the lock!" said Kirito. Now it's your duty to help Kirito, calculating in how many ways you can break the sequence into this format of integers?
The first line of the input data contains an integer T (1 ≤ T ≤ 100) specifying
the number of test cases.
For each test case there is a string of length at most 192, consisting of digits 0 to 9.
For each test case, output a single line containing the number of possible sequences mod by 1,000,000,007.