You must be familiar with the use of numeric keys to enter alphabets in mobile phones. A single numeric key when pressed gives a character. When pressed again, it changes to another and so on. Once the set of characters mapped to the key is exhausted, the key wraps around to the original character.

The key mapping in this problem is the T9 mapping, restricted to lowercase english characters. The characters corresponding to the individual keys are:

• 2: a,b,c
• 3: d,e,f
• 4: g,h,i
• 5: j,k,l
• 6: m,n,o
• 7: p,q,r,s
• 8: t,u,v
• 9: w,x,y,z

For example, if you press the key 2 once, it prints the character 'a'. On pressing it again, it becomes 'b', then 'c', then back to 'a' and so on.

Consider a string made of lowercase letters only. To enter this string into a mobile phone, a certain key sequence has to be entered with sufficient gaps in between. Suppose that the key sequence entered is correct but the gaps between keypresses are made arbitrarily. This can result in very different strings being printed.

For example, let the string to be input be "mod". The key sequence corresponding to this is 6_6663 where '_' denotes a gap between the keypresses. Suppose the keys are pressed in the same order, but with gaps between keypresses arbitrary. This can result in 8 different strings: "mod", "nnd", "omd", "mmmmd", "mnmd", "mmnd", "nmmd" and "md".

Given an input string, Find the number of possible strings printed by the key sequence corresponding to it.

Input

The first line of the input consists of T, the number of testcases (1≤T≤10). Following this are T lines, each containing a string. The string will consist only of lowercase letters and will have a maximum length of 100000

Output

For each string, output the number of strings corresponding to its key sequence. Since the answer can be very big, output it modulo 100000007

Example

Input:
2
mod
iopc
Output:
8
64