Holy Imperium of Independent Territories (HIIT) has been reigned over by many kings and queens. You have found a list of the regnal titles of all of the n monarchs that have ruled HIIT, and as is traditional, a regnal title consists of a regnal name followed by a regnal number. While the regnal numbers are typically written in Roman numerals, Uolevi has been kind and converted them to Arabic numerals for your convenience, i.e., the list has "Elizabeth 2" instead of "Elizabeth II".

The list does not describe the order in which the monarchs have ruled. It is fortunately well-known that if two monarchs share a regnal name, then the one with a smaller regnal number has to have ruled before the one with the larger one. You therefore wonder in how many different orders could the monarchs have possibly ruled.

Input

The first line of the input contains the number of monarchs, n.

The following n lines each contain a regnal name and a regnal number of a monarch, separated by a space. No regnal name contains spaces.

Output

Output a single integer, the number of different orders in which the monarchs could have ruled. Since the number can be large, output it modulo 10^9 + 7.

Constraints

• 1 \le n \le 10^5
• Each regnal number is an integer between 1 and 10^9.
• Each regnal name starts with an upper case character between 'A' and 'Z', possibly followed by some number of lower case characters between 'a' and 'z'.
• The total length of all regnal names in the input is at most 10^6.
• All regnal titles are unique.

Example

Input:

4
Uolevi 1
Maija 3
Uolevi 2
Maija 2

Output:

6