DMPG '19 S3 - Chemical Counting Capers

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem types

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

Comments

There are no comments at the moment.