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 1000$

Subtask 2 [50%]

$1\le N\le 1000000$

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