Marathon#3612
While watching the marathon races unfold on the streets of London, Vasya took some intriguing notes. For each pair of athletes passing by, he recorded the number if the second athlete's number was greater than the first, and if the opposite was true. Occasionally, Vasya got distracted and forgot the previous number, marking such instances in his notebook with the symbol '?'.
For instance, if the athletes passed Vasya in the sequence \{3,1,2,7,4,6,5\}, his notebook would read: "122121".
Your task is to determine how many permutations of the athletes' numbers could correspond to the sequence Vasya recorded. At the Olympics, athlete numbers were assigned consecutively starting from , and all athletes reached Vasya without dropping out.
Each test case is presented on a separate line and consists of a sequence of to characters, which may include only the digits '1', '2', or the symbol '?'. The input is guaranteed to be correct and free of leading or trailing spaces. The input continues until the end of the file.
For each test case, output the number of permutations of the athletes' numbers that match the sequence in Vasya's notebook, on a separate line. Since the result can be very large, provide the answer modulo .
Example 1