Chemical Code

题号：NC221784
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Chemical Code is an integrated development environment designed for chemists. Users can write the molecular formula in this editor, and if they move the mouse over the molecular formula, Chemical Code will display its relative molecular mass.

However, Moca, the developer of Chemical Code, did not implement this feature. Due to the tight schedule, she failed to meet the deadline, so that she just displayed the text "The relative molecular mass of CH3(CH2)2OH is 60.''.

The molecular formula that Chemical Code supports consists of three types of symbols -- chemical elements ( $C, H, O$ ), digits and parentheses. The relative molecular mass of $C$ is $12$ . The relative molecular mass of $O$ is $16$ . The relative molecular mass of $H$ is $1$ . The number written after a chemical element denotes that this element is repeated the corresponding number of times, and the number written after a pair of parentheses denotes where the subformula is also repeated the corresponding number of times. For example, $H2O$ is expanded as $HHO$ , and $(CH3)2$ is expanded as $(CHHH)2$ and $CHHHCHHH$ . Notice that nesting parentheses are allowed and multiple consecutive digits are not allowed. The relative molecular mass of a molecular formula is the sum of the relative molecular mass of all the chemical elements after expanding this molecular formula. The following is the context-free grammar of the molecular formula, and the start symbol is E.

To simplify this feature, Chemical Code can be formed as a character array of length $n$ , and it will handle the user's input operation. In the beginning, the array is initialized with $n$ null characters. The user will perform $q$ operations to fill the entire array. There are two types of the input operation. The first one is inputting a chemical element ( $C,H,O$ ) or a digit in the specified position. And the second one is inputting a pair of parentheses in two specified positions. After each operation, Chemical Code will erase the null characters and print the relative molecular mass of the current molecular formula, which can be derived in the above context-free grammar. It is guaranteed that each pair of parentheses input by the second type of operation is matching. For example, it is forbidden to input parentheses in the $2$ -nd and $5$ -th position in the molecular formula (␣C)␣.

Moca is asking for your help. Can you implement this feature for her?

输入描述:

The first line contains two integers   -- the length of the character array and the number of operations.

The next  lines describe the user's input operations, where the -th line contains one of two operations:

   ( is  or a digit except , ) -- user inputs a chemical element or a digit in the position ;
    -- user inputs a pair of parentheses in the position  and .

It is guaranteed that the user does not input characters in a position twice, and after all the operations, there is no null characters in the character array.

输出描述:

For each operation, print an integer in one line -- the relative molecular mass of the current molecular formula. Since the answer may be very large, you only need to print the answer modulo .

示例1

输入

复制

输出

复制

说明

The following table lists the answer of the above example.