Listing Passwords

Michael is the manager of a barely known office, and his room has a locker that holds the money for the employees. Unfortunately, Michael forgot the locker password, so it is now Dwight's job to help his boss. The password is a sequence of $N$ digits, each either 0 or 1. Michael remembers the value at some positions but not the whole password. He also remembers $M$ intervals of the password that are palindromes. He remembers palindromes well, for some reason. An interval is a palindrome if its first and last digits are equal, its second and second-to-last digits are equal, and so on. Dwight wants to know how hard it is to recover the whole password. He can calculate the number of possible passwords that match what Michael remembers. The answer may be very large, so output it modulo $10^9 + 7$.

The first line contains two integers $N$ and $M$ ($1 \le N \le 3 \times 10^5$, $1 \le M \le 3 \times 10^5$). The second line contains a string of $N$ characters $s_i$. If $s_i$ is 0 or 1, the $i$-th digit of the password is that value. If $s_i$ is ?, Michael does not remember the $i$-th digit. Each of the next $M$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le N$), meaning the part of the password from position $l_i$ to position $r_i$, inclusive, is a palindrome.

If Michael's memories conflict so that no password satisfies all of them, output 0. Otherwise, output the number of passwords that satisfy all of them, modulo $10^9 + 7$.