Divisible by 15 - Part 2
Problem
You are provided with a big number N( a string of digits ) .
You need to find the number of ways to partition it into strings such that every partitioned string of number is divisible by 15.
Note that no partitioned string should start with leading zeroes (although the partitioned number can be 0 itself).
Print Answer Modulo 109+7
Input Format:-
First Line will contain an integer T denoting the number of test cases.
Each test case will contain one string, i.e. the big integer N.
Output Format:-
Output the answer in new line for each test case.
Constraints:-
1 ≤ T ≤ 100
1 ≤ length of string (N) ≤ 105
Sum of N over all test cases ≤ 105
Time Limit: 1
Memory Limit: 256
Source Limit:
