MYQ3 - The Dating Dress Problem

Gauthami has to get dressed for a date. She is going to meet Prasanna in the poshest restaurant in the country of Thuvax.
Prasanna arrives early and sees the outfit she has picked.  
While waiting outside, Prasanna being a restless nerd calculates the number of ways she can get dressed.
 
The complete outfit she picks is represented as a string of digits. The digits represent the following details about the apparel:
(apparel = clothing or accessories or any other part of the outfit)
 
1 - a 2 piece apparel where first piece has to be worn before the other. It is followed by the description of the two pieces in order.
 
2 - a 2 piece apparel which can be worn in any order, and it is not necessary to complete one apparel before starting another one. It is followed by the description of the two pieces in order.
 
0 - a single piece of apparel which can be put on directly.
 
Help Prasanna calculate the number of ways in which Gautami can get dressed. Since Prasanna does not want to make Gauthami bored by telling her a huge number, he wants to tell her the number of ways modulo 1000000007.
 
For example, consider an outfit comprising of a shirt, a skirt into which the shirt has to be tucked in and  
a neck cloth worn over the shirt.
It will be represented as 10200 and the number of ways she can get dressed is 2(She has to wear the shirt first after which she can wear either the skirt after the neck cloth or neck cloth after the skirt).

Input

 

First line is a positive integer T (T<=100) representing the number of testcases 
It is followed by T lines, each containing a string S of digits (each digit will be one of 0,1,2) describing the outfit, 1<=|S|<=100,000
The complete outfit comprises of a single item.

First line is a positive integer T (T<=100) representing the number of testcases 

It is followed by T lines, each containing a string S of digits (each digit will be one of 0,1,2) describing the outfit, 1<=|S|<=100,000

The complete outfit comprises of a single item.

 

Output

Output for each test case should consist of one line representing the number of ways in which Gauthami can get dressed modulo 1000000007.

Example

Input:
3 
10200
0
1102000 Output: 2
1
2

Added by:jack(chakradarraju)
Date:2012-02-14
Time limit:1s-1.614s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2012

hide comments
2014-08-09 09:09:20 Daga
getting tle with O(n) complexity....any solutions
2012-03-10 06:56:01 Daniel Ampuero
What would be the output for the input string 2220020020200?
2012-02-29 11:15:11 Mitch Schwartz
Hmm, I think the rules are not so clear. For example consider 2200200. This could correspond to: a pair of gloves and a pair of socks. Now, can she put on first one sock, then one glove, then the other sock, then the other glove? Or must she complete one pair before starting the other?

And is 2200200 equivalent to 200200?

Well, hidden in there is another question: Is 200200 a valid string? It's not stated whether her "complete outfit" comprises a single item, or possibly a set of disjoint items. In the sample input we see only single items.

Yet another question: Is the empty string allowed? (I suppose it would mean she's naked, heh. But technically it doesn't contradict anything else in the problem statement.)

edit: Updated the question

Last edit: 2012-02-29 11:19:47
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.