408954: GYM103388 L Listing Passwords

Michael is the manager of a barely known office and inside his room there is a locker with the money to pay the employees. Unfortunately, Michael forgot the password of the locker and it is now Dwight's responsibility to help his boss.

The password is a sequence of $$$N$$$ digits, containing only zeroes and ones, and Michael remembers the value at some positions of the sequence, but not the whole password. Michael also remembers $$$M$$$ intervals of the password that are palindromes – his mind memorizes palindromes, for some reason.

An interval is a palindrome if, and only if, the first and last digits of the interval are equal, the second and second to last digits are equal, and so on.

Now Dwight wants to know how hard it will be to recover the whole password. You can help Dwight by calculating the number of possible passwords that follow what Michael remembers.

Since the answer may be very large, output it modulo $$$10^{9}+7$$$.

The first line contains the two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 3 \times 10^5$$$, $$$1 \le M \le 3 \times 10^5$$$), representing how many digits the password has and the number of intervals Michael remembers as palindromes, respectively.

The second line contains $$$N$$$ characters $$$s_i$$$, representing what digit Michael remembers about each position of the password. If $$$s_i$$$ is '$$$0$$$' or '$$$1$$$', then the $$$i$$$-th digit of the password is $$$0$$$ or $$$1$$$, respectively. If $$$s_i$$$ is '?', then Michael doesn't 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$$$), which means that the interval of the password from the digit at position $$$l_i$$$ to the digit at position $$$r_i$$$, inclusive, is a palindrome.

Output the number of possible passwords that form a valid password modulo $$$10^{9}+7$$$. Since some of Michael's memories may be conflicting, in case there are no passwords that follow all his memories, print '0'.

5 2
1??0?
1 3
2 4

2

3 2
???
1 1
1 3

4

5 2
1???0
1 3
3 5

0