atcoder#ASAPOROB. 圧縮
圧縮
Score : points
Problem Statement
Takahashi found an integer sequence with terms. Since it was too heavy to carry, he decided to compress it into a single integer.
The compression takes place in steps, each of which shorten the length of the sequence by . Let be a string describing the steps, and the sequence on which the -th step is performed be , then the -th step will be as follows:
- When the -th character in is
M
, let , and replace the current sequence by . - When the -th character in is
m
, let , and replace the current sequence by .
Takahashi decided the steps , but he is too tired to carry out the compression. On behalf of him, find the single integer obtained from the compression.
Constraints
- consists of characters.
- Each character in is either
M
orm
.
Partial Scores
- In the test set worth points, there exists such that the first characters in are
M
, and the remaining characters arem
, that is, is in the formM...Mm...m
. - In the test set worth points, the odd-number-th characters in are
M
, and the even-number-th characters arem
, that is, is in the formMmMmMm...
.
Input
The input is given from Standard Input in the following format:
…
Output
Print the single integer obtained from the compression.
4
1 2 3 4
MmM
3
The initial sequence is compressed as follows:
- After the first step, the sequence is .
- After the second step, the sequence is .
- After the third step, the sequence is .
Thus, the single integer obtained from the compression is .
5
3 4 2 2 1
MMmm
2
10
1 8 7 6 8 5 2 2 6 1
MmmmmMMMm
5
20
12 7 16 8 7 19 8 19 20 11 7 13 20 3 4 11 19 11 15 5
mMMmmmMMMMMMmMmmmMM
11