Sum of Powers

You are given an integer (N) and (N) pairs of integers. Each pair contains a base (b) and an exponent (e). Your task is to compute (b^e \mod (10^9+7)) for each pair and then calculate the sum of all these values, also taken modulo (10^9+7).

The problem can be mathematically defined as follows:

[ \text{result} = \left( \sum_{i=1}^{N} b_i^{e_i} \right) \mod (10^9+7) ]
Note that by convention, (0^0) is treated as 1.

inputFormat

The first line of input contains one integer (N), representing the number of pairs. The following (N) lines each contain two space-separated integers (b) and (e), representing the base and the exponent.

outputFormat

Output a single integer, which is the sum of (b^e) computed for each pair modulo (10^9+7).## sample

1
2 3

8