IOPC1203 - Crazy texting

no tags 

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

hide comments
nadstratosfer: 2018-02-03 05:04:32

5 mins to figure out how to solve it, 20mins refactoring to beat TLE in Python and then almost 2 hours hunting for the most elusive bug I've committed in months.. So exhausted..

NEXES: 2014-12-06 11:02:27

My 50th on spoj after getting so many wrong ans finally AC............ great problem

Last edit: 2014-12-06 11:03:08
`Ak: 2014-08-17 14:51:04

@Raziman T V getting wa on running judge (13)
pls check my submission id is 12171190

(reply by cyclops) Judging does not halt on first failure. This means that if you see "Running... (13)", you cannot assume your code was correct and fast enough for 0 through 12.

Last edit: 2014-08-18 07:12:30
Apoorv Jindal: 2014-01-08 13:57:25

Thanks to the problem setter :) Great problem, strong test suite.


Added by:Raziman T V
Date:2012-01-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:http://www.codechef.com/IOPC2012/