A holiday tradition in Woburn C.I. is to give each other boxen (boxes). However, these are no ordinary boxen, they contains gifts, such as foxen (foxes) or more boxen. When one receives a fox, they gain a happiness of , a constant given at the beginning of the input. You have one species of foxen and a number of different species of boxen.

These boxen have strange properties, they contain exactly one fox or box (which may in turn contain more boxen), regardless of size. No box can directly or indirectly contain itself. Each box has a difficulty value , and multiplier value . The happiness given in a box is equal to the following formula:

Where is the happiness of the box (or fox) that it contains.

boxen. For index , would like to know the maximum happiness that can be created by packing zero or more boxen (and also a single fox), in any order, that are listed before or on that index. Note that if you use zero boxen, the happiness is just .

has a list of#### Input Specification

integers, and .

lines, each with integers: and .

#### Output Specification

lines, each with an integer: the answer to each of 's queries. **Since the answer can be large, please output the value modulo **.

#### Sample Input

```
2 3
2 8
7 12
```

#### Sample Output

```
3
10
```

## Comments

According to the statement, answer for each query can be about 1e5 ^ 1e5 (5e5 digits). But we need to output about 1e5 so big numbers, which is obviously impossible.

You should output the result modulo . I will update the statement shortly, sorry for the inconvenience.