Problem Statement

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)$?

Constraints

• $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}$

Input

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

N M
S
l_1 r_1
:
l_M r_M

Output

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