311372: CF1975I. Mind Bloom

I. Mind Bloomtime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputThis is the way it always was. This is the way it always will be. All will be forgotten again soon...

Jellyfish is playing a one-player card game called "Slay the Spire". There are $n$ cards in total numbered from $1$ to $n$. The $i$-th card has power $c_i$.

There is a binary string $s$ of length $n$. If $s_i = \texttt{0}$, the $i$-th card is initially in the draw pile. If $s_i = \texttt{1}$, the $i$-th card is initially in Jellyfish's hand.

Jellyfish will repeat the following process until either her hand or the draw pile is empty.

1. Let $x$ be the power of the card with the largest power in her hand.
2. Place a single card with power $x$ back into the draw pile.
3. Randomly draw $x$ cards from the draw pile. All subsets of $x$ cards from the draw pile have an equal chance of being drawn. If there are fewer than $x$ cards in the draw pile, Jellyfish will draw all cards.

At the end of this process, find the probability that Jellyfish can empty the draw pile, modulo $1\,000\,000\,007$.

Formally, let $M=1\,000\,000\,007$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\leq t\leq 100$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 120$) — the number of cards.

The second line of each test case contains $n$ integers $c_1,c_2,\ldots,c_n$ ($0 \leq c_i \leq n$) — the powers of the cards. It is guaranteed that $c_1 \leq c_2 \leq \ldots \leq c_n$.

The third line of each test case contains a binary string $s$ of length $n$. If $s_i = \texttt{0}$, the $i$-th card is initially in the draw pile. If $s_i = \texttt{1}$, the $i$-th card is initially in Jellyfish's hand.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $120^2$.

Output

For each test case, output the probability that Jellyfish can empty the draw pile modulo $1\,000\,000\,007$.

ExampleInput

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

Output

500000004
0
0
675898154

Note

In the first test case, Jellyfish will keep playing cards with power $1$ until Jellyfish draws a card with power $0$ or power $2$. If Jellyfish draws a card with power $0$, she will eventually empty her hand. If Jellyfish draws a card with power $2$, she will eventually empty the draw pile. Since there is an equal chance of drawing $0$ or $2$, the answer is $\frac{1}{2}$, and $2 \cdot 500\,000\,004 \equiv 1 \pmod {10^9+7}$

题目大意：
Jellyfish 在玩一款名为 "Slay the Spire" 的单人卡牌游戏。总共有 n 张卡牌，从 1 到 n 编号，第 i 张卡牌具有功率 c_i。有一个长度为 n 的二进制字符串 s，如果 s_i = '0'，则第 i 张卡牌最初在抽牌堆中；如果 s_i = '1'，则第 i 张卡牌最初在 Jellyfish 的手中。

Jellyfish 将重复以下过程，直到她的手牌或抽牌堆为空：
1. 令 x 为她手中功率最大的卡牌的功率。
2. 将一张功率为 x 的卡牌放回抽牌堆。
3. 从抽牌堆中随机抽取 x 张卡牌。从抽牌堆中抽取 x 张卡牌的所有子集都有相同的概率被抽到。如果抽牌堆中的卡牌少于 x 张，Jellyfish 将抽取所有卡牌。

在此过程结束时，求 Jellyfish 能够清空抽牌堆的概率，模 1,000,000,007。

输入输出数据格式：
输入：
- 第一行包含一个整数 t（1≤t≤100），表示测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含一个整数 n（1≤n≤120）——卡牌的数量。
- 第二行包含 n 个整数 c_1,c_2,…,c_n（0≤c_i≤n）——卡牌的功率。保证 c_1≤c_2≤…≤c_n。
- 第三行包含一个长度为 n 的二进制字符串 s。如果 s_i = '0'，则第 i 张卡牌最初在抽牌堆中；如果 s_i = '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 的卡牌，直到 Jellyfish 抽到功率为 0 或 2 的卡牌。如果 Jellyfish 抽到功率为 0 的卡牌，她最终将清空手牌。如果 Jellyfish 抽到功率为 2 的卡牌，她最终将清空抽牌堆。由于抽到 0 或 2 的概率相等，答案是 1/2，且 2 * 500,000,004 ≡ 1 (mod 10^9+7)。题目大意： Jellyfish 在玩一款名为 "Slay the Spire" 的单人卡牌游戏。总共有 n 张卡牌，从 1 到 n 编号，第 i 张卡牌具有功率 c_i。有一个长度为 n 的二进制字符串 s，如果 s_i = '0'，则第 i 张卡牌最初在抽牌堆中；如果 s_i = '1'，则第 i 张卡牌最初在 Jellyfish 的手中。 Jellyfish 将重复以下过程，直到她的手牌或抽牌堆为空： 1. 令 x 为她手中功率最大的卡牌的功率。 2. 将一张功率为 x 的卡牌放回抽牌堆。 3. 从抽牌堆中随机抽取 x 张卡牌。从抽牌堆中抽取 x 张卡牌的所有子集都有相同的概率被抽到。如果抽牌堆中的卡牌少于 x 张，Jellyfish 将抽取所有卡牌。 在此过程结束时，求 Jellyfish 能够清空抽牌堆的概率，模 1,000,000,007。 输入输出数据格式： 输入： - 第一行包含一个整数 t（1≤t≤100），表示测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含一个整数 n（1≤n≤120）——卡牌的数量。 - 第二行包含 n 个整数 c_1,c_2,…,c_n（0≤c_i≤n）——卡牌的功率。保证 c_1≤c_2≤…≤c_n。 - 第三行包含一个长度为 n 的二进制字符串 s。如果 s_i = '0'，则第 i 张卡牌最初在抽牌堆中；如果 s_i = '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 的卡牌，直到 Jellyfish 抽到功率为 0 或 2 的卡牌。如果 Jellyfish 抽到功率为 0 的卡牌，她最终将清空手牌。如果 Jellyfish 抽到功率为 2 的卡牌，她最终将清空抽牌堆。由于抽到 0 或 2 的概率相等，答案是 1/2，且 2 * 500,000,004 ≡ 1 (mod 10^9+7)。