There is a string `S` of length `N` consisting of characters `0`

and `1`

. You will perform the following operation for each `i = 1, 2, ..., m`:

- Arbitrarily permute the characters within the substring of
`S`starting at the`l_i`-th character from the left and extending through the`r_i`-th character.

Here, the sequence `l_i` is non-decreasing.

How many values are possible for `S` after the `M` operations, modulo `1000000007(= 10^9+7)`?

`2≦N≦3000``1≦M≦3000``S`consists of characters`0`

and`1`

.- The length of
`S`equals`N`. `1≦l_i < r_i≦N``l_i ≦ l_{i+1}`

The input is given from Standard Input in the following format:

NMSl_1r_1:l_Mr_M

Print the number of the possible values for `S` after the `M` operations, modulo `1000000007`.

5 2 01001 2 4 3 5

6

After the first operation, `S` can be one of the following three: `01001`

, `00101`

and `00011`

.

After the second operation, `S` can be one of the following six: `01100`

, `01010`

, `01001`

, `00011`

, `00101`

and `00110`

.

9 3 110111110 1 4 4 6 6 9

26

11 6 00101000110 2 4 2 3 4 7 5 6 6 10 10 11

143

Subtask | Score |
---|---|

1 | 100 |

2 | 0 |