Mr X likes to play string games.
Mr X has an operation sequence. This operation sequence can be written as a string. For each operation, the next character of the operation sequence can be inserted before or after the current string. For example, my operation sequence is "aabac", suppose the sequence obtained after the first four operations is "baaa", then after the last operation, the string may become "baaac" or "cbaaa". It can be seen that there is only one operation method for the first operation. For other operations, there are only two methods of operation.
For each operation method, there will be a score. The smaller the lexicographic order of the final string, the higher the final score.
Then, for a given operation sequence, how many operation methods can get the maximum score.
The two operation methods are different. If and only if there is a certain operation (not the first operation), one operation will be inserted before the current string, and the other operation will be inserted after the current string.