Marathon
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 2 if the second athlete's number was greater than the first, and 1 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 2012 Olympics, athlete numbers were assigned consecutively starting from 1, and all athletes reached Vasya without dropping out.
Input
Each test case is presented on a separate line and consists of a sequence of 1 to 1000 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.
Output
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 20122013.