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 n atoms of the element represented by E.
• ~X =~ ( A ) n, where A is a valid chemical formula, indicating that the number of atoms of each element in A must be multiplied by n.
• ~X =~ A B, where A and B are valid chemical formulas. The number of atoms of each element E in ~X~ equals the number of atoms of E in A plus the number of atoms of E in B.

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?

Constraints

Subtask 1 [50%]

~1 \le N \le 1\,000~

Subtask 2 [50%]

~1 \le N \le 1\,000\,000~

Input Specification

The first line contains one integer, ~N~.
The second line contains a valid chemical formula consisting of ~N~ space-separated components.

Output Specification

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