I. Mind Bloom
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод
This is the way it always was.
This is the way it always will be.
All will be forgotten again soon...

Jellyfish играет в карточную игру для одного игрока под названием «Slay the Spire». Всего есть $$$n$$$ карт, пронумерованных от $$$1$$$ до $$$n$$$. У $$$i$$$-й карты есть сила $$$c_i$$$.

Дана бинарная строка $$$s$$$ длины $$$n$$$. Если $$$s_i = \texttt{0}$$$, то $$$i$$$-я карта изначально находится в колоде. Если $$$s_i = \texttt{1}$$$, то $$$i$$$-я карта изначально находится в руке Jellyfish.

Jellyfish будет повторять следующий процесс до тех пор, пока либо её рука, либо колода не опустеют:

  1. Пусть $$$x$$$ — это сила карты с наибольшей силой в руке.
  2. Поместить одну карту с силой $$$x$$$ обратно в колоду.
  3. Случайным образом взять $$$x$$$ карт из колоды. Все подмножества $$$x$$$ карт из колоды имеют равные шансы быть вытянутыми. Если в колоде меньше $$$x$$$ карт, Jellyfish вытянет все карты.

Найдите вероятность того, что Jellyfish сможет опустошить колоду в конце этого процесса, по модулю $$$1\,000\,000\,007$$$.

Формально, пусть $$$M=1\,000\,000\,007$$$. Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x < M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\leq t\leq 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 120$$$) — количество карт.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$c_1,c_2,\ldots,c_n$$$ ($$$0 \leq c_i \leq n$$$) — силы карт. Гарантируется, что $$$c_1 \leq c_2 \leq \ldots \leq c_n$$$.

Третья строка каждого набора входных данных содержит бинарную строку $$$s$$$ длины $$$n$$$. Если $$$s_i = \texttt{0}$$$, то $$$i$$$-я карта изначально находится в колоде. Если $$$s_i = \texttt{1}$$$, то $$$i$$$-я карта изначально находится в руке Jellyfish.

Гарантируется, что сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$120^2$$$.

Выходные данные

Для каждого набора входных данных выведите вероятность того, что Jellyfish сможет опустошить колоду, по модулю $$$1\,000\,000\,007$$$.

Пример
Входные данные
4
5
0 1 1 1 2
00100
3
2 3 3
000
10
0 0 0 0 0 0 0 1 1 1
1111011111
20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 3 3 4
00000000001000101010
Выходные данные
500000004
0
0
675898154
Примечание

В первом наборе входных данных Jellyfish будет продолжать играть картами с силой $$$1$$$ до тех пор, пока не вытянет карту с силой $$$0$$$ или с силой $$$2$$$. Если Jellyfish вытянет карту с силой $$$0$$$, она в конце концов опустошит свою руку. Если Jellyfish вытянет карту с силой $$$2$$$, она в итоге опустошит колоду. Поскольку шансы вытянуть $$$0$$$ или $$$2$$$ равны, ответ будет $$$\frac{1}{2}$$$, а $$$2 \cdot 500\,000\,004 \equiv 1 \pmod {10^9+7}$$$.