CF1975I.Mind Bloom

这就是一切一直以来的样子。

这也将是未来永远的样子。

一切很快又会被遗忘……

Jellyfish 正在玩一款单人卡牌游戏“Slay the Spire”。共有 $n$ 张卡牌，编号从 $1$ 到 $n$。第 $i$ 张卡牌的力量为 $c_i$。

有一个长度为 $n$ 的二进制字符串 $s$。如果 $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$。

第三行包含一个长度为 $n$ 的二进制字符串 $s$。如果 $s_i = \texttt{0}$，第 $i$ 张卡牌最初在抽牌堆中；如果 $s_i = \texttt{1}$，第 $i$ 张卡牌最初在 Jellyfish 的手牌中。

保证所有测试用例的 $n^2$ 之和不超过 $120^2$。

对于每组测试数据，输出 Jellyfish 能将抽牌堆清空的概率，对 $1\,000\,000\,007$ 取模。

在第一个测试用例中，Jellyfish 会不断打出力量为 $1$ 的卡牌，直到她抽到一张力量为 $0$ 或 $2$ 的卡牌。如果她抽到力量为 $0$ 的卡牌，最终她会将手牌打空。如果她抽到力量为 $2$ 的卡牌，最终她会将抽牌堆清空。由于抽到 $0$ 或 $2$ 的概率相等，答案为 $\frac{1}{2}$，而 $2 \cdot 500\,000\,004 \equiv 1 \pmod {10^9+7}$。

由 ChatGPT 4.1 翻译