Forgot Password ?
New password will be sent to following email id
Problem Code : CARNAVAL
1 14 red yellow green red yellow green red blue orange ? ? ? ? ?
Time Limit :
C , C++ , Java , Python 2
Login to submit your response.
Buddy and Tomo decide to visit the annual Carnaval in the Netherlands together! These are at least 4 days of festivities with lots of songs, fun and a big parade in each town. <br><br> <iframe width="560" height="315" src="https://www.youtube.com/embed/jHdMPtq7CFI" frameborder="0" allowfullscreen></iframe> <br><br> They go to watch the parade, and Buddy notices each person is wearing a costume of a specific color. He had a little bit too much to drink and doesn't pay attention all the time, however afterwards, Tomo tells him that, since the festival colors of Carnaval are <i>red</i>, <i>yellow</i> and <i>green</i>, that there was no other color that appeared more often than <i>red</i>, <i>yellow</i> or <i>green</i>. Moreover, <i>red</i>, <i>yellow</i> and <i>green</i> all appeared equally many times. <br><br> Now, Buddy wants to derive the number of possible ways the parade could have looked, based on his observations. He assumes that he noticed each color that appears in the parade at least once. Basically, he wants to know in how many ways he can assign one of the colors he saw to each of the people that he did not see the color of. He does not care about the order (see output description and sample explanation).
The first line has a number <b>T</b>, the number of test cases. After this, <b>T</b> test cases follow.<br> Each test case starts with a line with an integer <b>N</b>: the number of people in the parade. Next, <b>N</b> lines follow, each with a string denoting the color of the costume of the <b>i</b><sup>th</sup> person in the parade (in the order that the people walked in the parade): <ul> <li><i>?</i> if Buddy was not paying attention when this person was passing</li> <li>A string <b>S</b> consisting only of lowercase letters (with 1 ≤ |<b>S</b>| ≤ 10) if Buddy saw the person was wearing a costume of color <b>S</b></li> </ul><br> It is guaranteed that Buddy noticed at least one person with <i>red</i>, at least one person with <i>yellow</i> and at least one person with <i>green</i> on.
For each test case, output one line with the number of ways the parade could have looked. Two parades are considered different when for some color they have a different amount of people wearing a costume of that color. This means that two parades are considered the same when one is a permutation of the other. <br><br> For your convenience, it is guaranteed that the answer for each test case is strictly positive, and never larger than 10<sup>9</sup>.
1 ≤ <b>T</b> ≤ 100 <br> 2 ≤ <b>N</b> ≤ 1000 <br> 3 ≤ number of different colors per test case (including <i>red</i>, <i>yellow</i> and <i>green</i>) ≤ 10
The possible ways to assign colors to the people are: <ul> <li><i>red</i>, <i>yellow</i>, <i>yellow</i>, <i>green</i>, <i>green</i></li> <li><i>yellow</i>, <i>green</i>, <i>blue</i>, <i>blue</i>, <i>orange</i></li> <li><i>yellow</i>, <i>green</i>, <i>blue</i>, <i>orange</i>, <i>orange</i></li> </ul>