A chemical formula is a way of presenting information about the elements present in a molecule. Each distinct element in the formula is uniquely represented by a symbol, a string consisting either of one uppercase English letter or one uppercase followed by one lowercase English letter. There are three types of components that may be present in a chemical formula:
E n, a valid symbol followed by a positive integer no greater than ~10^9~.
(, an opening parenthesis.
) n, a closing parenthesis followed by a positive integer no greater than ~10^9~.
A chemical formula ~X~ is valid if and only if:
- ~X =~
E n, indicating that there are
natoms of the element represented by
- ~X =~
( A ) n, where
Ais a valid chemical formula, indicating that the number of atoms of each element in
Amust be multiplied by
- ~X =~
A B, where
Bare valid chemical formulas. The number of atoms of each element
Ein ~X~ equals the number of atoms of
Aplus the number of atoms of
Dr. Henri is observing a chemical formula made of ~N~ components and wants to know the number of atoms of each element present in it. Since these numbers may be very large, he would like to know their values mod ~10^9 + 7~. Can you help him?
Subtask 1 [50%]
~1 \le N \le 1\ 000~
Subtask 2 [50%]
~1 \le N \le 1\ 000\ 000~
The first line contains one integer, ~N~.
The second line contains a valid chemical formula consisting of ~N~ space-separated components.
Output ~K~ lines, where ~K~ is the number of distinct elements present in the formula. Each line should be of the form
a b, where
a is the symbol of the element and
b is the number of atoms of that element mod ~10^9 + 7~. Please output the symbols in lexicographically increasing order.
Sample Input 1
4 ( C 1 Cl 4 ) 2
Sample Output 1
C 2 Cl 8
Sample Input 2
8 ( Co 1 ( N 1 H 3 ) 6 ) 2 Cl 3
Sample Output 2
Cl 3 Co 2 H 36 N 12