406875: GYM102591 C Проспект со светофорами

Однажды Абаю приснилось, как он был мэром города. В один из дней на главном проспекте Абая случилась проблема — некоторые светофоры сломались. Всего на проспекте есть $$$N$$$ перекрестков, пронумерованных от $$$1$$$ до $$$N$$$ от начала до конца проспекта. На каждом перекрестке есть по одному светофору. Абаю необходимо починить все сломанные светофоры, для этого существует $$$M$$$ бригад, $$$i$$$-я бригада чинит все светофоры с номерами от $$$L_i$$$ до $$$R_i$$$ включительно. Разрешается чинить один и тот же светофор сколько угодно раз, даже если светофор изначально не сломан. Главное условие — каждый сломанный светофор должны починить хотя бы 1 раз. Абаю стало интересно — сколько есть различных наборов бригад, которые могут починить все сломанные светофоры. Два набора бригад считаются различными, если в одном наборе есть такая бригада, которой нет в другом наборе. Так как ответ может быть довольно огромным, выведите его остаток от деления на $$$10^9 + 7$$$.

В первой строке входных данных задано натуральное число $$$N$$$ — количество перекрестков ($$$1 \leq N \leq 5000$$$).

Во второй строке задается бинарная строка длины $$$N$$$, состоящая из символов 0 или 1. $$$i$$$-й символ в строке равен 0, если $$$i$$$-й светофор сломан, иначе 1.

В третьей строке дается целое число $$$M$$$ — количество бригад ($$$1 \leq M \leq 5000$$$).

Далее идут $$$M$$$ строк, каждая из них содержит по 2 числа $$$L_i$$$ и $$$R_i$$$ — описание $$$i$$$-й бригады ($$$1 \leq L_i \leq R_i \leq N$$$).

Гарантируется, что не существует двух разных бригад $$$i$$$ и $$$j$$$, что $$$L_i = L_j$$$ и $$$R_i = R_j$$$.

Выведите единственное число — количество подходящих наборов бригад по модулю $$$10^9 + 7$$$.

4
0000
2
1 4
2 3

2