Our warmest thanks for this problem to Clive Fraser aka CSFPython!
It was a bright sunny day when Freddie the frog set off to find his friend Percy the Pixie. Percy usually had a new puzzle for Freddie to solve, so Freddie was keen to find out what Percy had devised for him this time. As he came up to his favourite pond Freddie was surprised to see a line of lily pads going across the pond, and even more surprised to find that each lily pad had a number on it. He was not surprised to find Percy with a wide grin on his face.
Percy explained that each of the lily pads had a single digit number on it (in the range 0 to 9). Percy said that the puzzle was about palindromes. These are sequences that read the same forwards and backwards. So 35453 and 2992 are palindromes but 1121 is not. Percy said that Freddie had to find a route across the pond by hopping between lily pads so that each hop was over a palindromic sequence of digits. For example, if we have the sequence of lily pads 4, 7, 4, 5, 6 and Freddie is currently on the leftmost pad (4) he must look for a palindromic sequence starting from the pad that he is currently on. The sequence 4,7,4 is a palindrome of length 3 so Freddie can hop over 3 lily pads to land on the 5. Note that Freddie cannot make a hop to the central 4 because 4,7 is not a palindrome. Nor can he make a hop to the 6 because 4,7,4,5 is not a palindrome.
After thinking about the rules, Freddie pointed out that a single digit is also a palindrome. This means that he can cross the pond by using all of the lily pads and only taking hops of length 1. Percy looked really crestfallen at this news but Freddie had a good idea to cheer him up. Freddie said that there would always be at least one way to cross the pond but it was quite likely that there would be a large number of different ways to cross it. He suggested that the puzzle should be to work out how many different ways there are to cross the pond. Percy was delighted with this idea and immediately set about designing some puzzles for Freddie to solve.
The first puzzle was deliberately easy. Percy created the sequence 53686340771 using 11 lily pads. One way that Freddie could cross the pond can be represented by 5 36863 4 0 77 1 which requires seven jumps for Freddie to cross the pond. The first jump must be from the bank to the first lily pad (5). Freddie then makes a jump of length 1 to land on 3. He is now at the start of the palindrome 36863 so he can jump over this palindrome to land on 4. Two more single-step jumps take him to 7. He is now at the start of palindrome 77 so can make a jump of size 2 to reach 1. Finally he makes a single-step jump to the bank of the pond. It is fairly easy to show that there are six different ways of crossing the pond for this puzzle. These are shown below, using the same method as that used above, to indicate the individual jumps.
5 36863 4 0 77 1
5 3 686 3 4 0 77 1
5 3 6 8 6 3 4 0 77 1
5 36863 4 0 7 7 1
5 3 686 3 4 0 7 7 1
5 3 6 8 6 3 4 0 7 7 1
The first line of the problem will be a single integer N denoting the number of puzzles to solve. Each of the following N lines will hold a single string of digits to represent the puzzle. For each string of digits you need to work out the number of different ways of crossing the pond. As this can increase quite rapidly, all answers should be given modulo 1000000007 (10^9 + 7). Give these answers, separated by spaces, as a single string.
Example:
input:
3
53686340771
629503751963497
37939785599119955555732222200223322009999960158511177111875
answer:
6 1 186913273