23398번 - 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⁹ + 7.

입력

The first line contains the two integers N and M (1 ≤ N ≤ 3×10⁵, 1 ≤ M ≤ 3×10⁵), 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 ≤ l_i ≤ r_i ≤ 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⁹ + 7. Since some of Michael’s memories may be conflicting, in case there are no passwords that follow all his memories, print ‘0’.

제한

힌트