Serena is learning about binary numbers in math class! She is given a binary number , and she is also given series of operations which she must perform on it. In one operation, she sets all bits in the 1-indexed range to , and outputs the base-10 value of the binary number, modulo .

The base-10 value of a binary number of length consisting of digits and is given by the sum of over all in .

#### Input Specification

The first line contains two space-separated integers, and , the length of the number and the number of operations.

The next line contains , the original binary number.

The next lines contain two space-separated integers, and , representing an operation described in the problem statement.

#### Output Specification

For each operation, output the base-10 value of the binary number after performing the operation, modulo .

#### Constraints

In all subtasks,

##### Subtask 1 [20%]

##### Subtask 2 [80%]

No additional constraints.

#### Sample Input 1

```
5 2
01000
1 3
2 4
```

#### Sample Output 1

```
28
30
```

## Comments