비밀번호 나열하기

마이클은 거의 알려지지 않은 사무실의 관리자이다. 그의 방에는 직원들에게 줄 돈이 든 금고가 있다. 안타깝게도 마이클은 금고 비밀번호를 잊어버렸고, 이제 상사를 돕는 일은 드와이트의 몫이다. 비밀번호는 0 또는 1로 이루어진 길이 $N$의 숫자열이다. 마이클은 일부 위치의 숫자만 기억하고 전체 비밀번호는 기억하지 못한다. 또한 비밀번호의 구간 $M$개가 회문이라는 사실을 기억한다. 그는 이유는 모르지만 회문을 잘 기억한다. 구간의 첫 숫자와 마지막 숫자가 같고, 두 번째 숫자와 끝에서 두 번째 숫자가 같으며, 이런 식으로 끝까지 같으면 그 구간은 회문이다. 드와이트는 비밀번호 전체를 복원하기가 얼마나 어려운지 알고 싶어 한다. 마이클의 기억에 맞는 비밀번호의 개수를 세면 그 답을 알 수 있다. 답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 줄에 두 정수 $N$과 $M$이 주어진다 ($1 \le N \le 3 \times 10^5$, $1 \le M \le 3 \times 10^5$). 둘째 줄에는 길이 $N$의 문자열 $s_i$가 주어진다. $s_i$가 0 또는 1이면 비밀번호의 $i$번째 숫자가 그 값이라는 뜻이다. $s_i$가 ?이면 마이클이 $i$번째 숫자를 기억하지 못한다는 뜻이다. 이어지는 $M$개의 줄에는 정수 $l_i$와 $r_i$가 주어지며($1 \le l_i \le r_i \le N$), 비밀번호의 $l_i$번째부터 $r_i$번째까지 구간(양 끝 포함)이 회문이라는 뜻이다.

마이클의 기억끼리 모순되어 모든 조건을 만족하는 비밀번호가 없으면 0을 출력한다. 그렇지 않으면 모든 조건을 만족하는 비밀번호의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.