{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"ICC World Cup 2011 has just finished. During the world cup, lots of cricket fans were playing an online game named \"Fantasy Cricket\".\n\nThe score board of fantasy cricket looks like the following table. After each match of the world cup, the score board of fantasy cricket gets updated.\n\n\n\n| Rank | | Manager | Team Name | Total |\n| :--: | -------------------------------------------------------------------- | :----------: | :-------------: | :---: |\n| 1 | \u003ci class\u003d\"mdi mdi-play has-text-success mdi-24px mdi-rotate-270\"\u003e\u003c/i\u003e| Mind the Gap | Mind the Gap XI | 12384 |\n| 2 | \u003ci class\u003d\"mdi mdi-play has-text-danger mdi-24px mdi-rotate-90\"\u003e\u003c/i\u003e | Old Man | Old Man XI | 12344 |\n| 3 | \u003ci class\u003d\"mdi mdi-play has-text-success mdi-24px mdi-rotate-270\"\u003e\u003c/i\u003e| Legend | Legend XI | 11611 |\n| 4 | \u003ci class\u003d\"mdi mdi-play has-text-danger mdi-24px mdi-rotate-90\"\u003e\u003c/i\u003e | Far Cry | Far Cry XI | 11221 |\n| 5 | \u003ci class\u003d\"mdi mdi-play has-text-info mdi-24px\"\u003e\u003c/i\u003e | AC | AC XI | 10111 |\n| 6 | \u003ci class\u003d\"mdi mdi-play has-text-success mdi-24px mdi-rotate-270\"\u003e\u003c/i\u003e| WA | WA XI | 10001 |\n\nTable 1\n\n\nEach player plays a role of a manager here. In the rank list there is a symbol besides each manger. There are three kinds of symbols. These are explained in the following table:\n\n\n\n| Symbol | Explanation | ASCII Representation |\n| ---------------------------------------------------------------------- | ----------- | -------------------- |\n| \u003ci class\u003d\"mdi mdi-play has-text-success mdi-rotate-270 mdi-48px\"\u003e\u003c/i\u003e | The rank of the player has upgraded after the last match, i.e. if the current rank of the player is **K**, the rank of the player before the last match was greater than **K**. | **U** |\n| \u003ci class\u003d\"mdi mdi-play has-text-danger mdi-rotate-90 mdi-48px\"\u003e\u003c/i\u003e | The rank of the player has downgraded after the last match, i.e. if the current rank of the player is **K**, the rank of the player before the last match was less than **K**. | **D** |\n| \u003ci class\u003d\"mdi mdi-play has-text-info mdi-48px\"\u003e\u003c/i\u003e | The rank of the player has not changed after the last match, i.e. if the current rank of the player is **K**, the rank of the player before the last match was also **K**.. | **E** |\n\n\n\nYou will be given such a score board after a particular match. Can you determine any possible valid ordering of the players exactly before that round? For this problem you have to print the number of possible ordering before the last match.\n\nHere is an example:\n\n\n\n| Rank | | Manager |\n| :--: | ----------------------------------------------------------------------- | :-----: |\n| 1 | \u003ci class\u003d\"mdi mdi-play has-text-success mdi-24px mdi-rotate-270\"\u003e\u003c/i\u003e | A |\n| 2 | \u003ci class\u003d\"mdi mdi-play has-text-danger mdi-24px mdi-rotate-90\"\u003e\u003c/i\u003e | B |\n| 3 | \u003ci class\u003d\"mdi mdi-play has-text-success mdi-24px mdi-rotate-270\"\u003e\u003c/i\u003e | C |\n| 4 | \u003ci class\u003d\"mdi mdi-play has-text-danger mdi-24px mdi-rotate-90\"\u003e\u003c/i\u003e | D |\n\nTable 2\n\n\n\n\n| Possible Previous Order 1 | Possible Previous Order 2 |\n| :-----------------------: | :------------------------: |\n| B | B |\n| A | D |\n| D | A |\n| C | C |\n\nTable 3\n\n\nFor this rank (table 2), only two different ordering are possible (table 3) before the last match which comply the current ordering with the symbols.\n\nName of the managers are not important for this problem. So, for a scoreboard, you will be given a sequence of ASCII representation of the symbols (stated above), i.e. you will be given a string which only contains **\u0027U\u0027, \u0027D\u0027** and **\u0027E\u0027**."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 300)**, denoting the number of test cases.\n\nEach case starts with a line containing a string. The length of the string will be between **1** and **1000**. The string will contain characters from **{\u0027U\u0027, \u0027D\u0027, \u0027E\u0027}**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the number of possible orderings modulo **1000000007 (10\u003csup\u003e9\u003c/sup\u003e + 7)**."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\nUDUD\nEEE\nDU\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 2\nCase 2: 1\nCase 3: 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}