题目描述

很久以前，Markyzy 发明了一个名为 "Hello World" 的问题。

后来，Markyzy 发明了一个名为 "Hello World 2" 的问题，它是 "Hello World" 的一个更难版本。

两千年后，SPY 发明了一个名为 "Hello World 3" 的问题，它是 "Hello World" 的一个更难版本。

现在，SPY 正在发明一个名为 "Hello World 3 Pro Max" 的问题，它是 ...

SPY 有一个长度为 $n$ 的字符串 $S$，由小写字母组成：$h, e, l, o, w, r, d$。该字符串是按照以下方式随机生成的：对于 $S$ 中的每个字符，它独立地从集合 $\{h,e,l,o,w,r,d\}$ 中生成，生成概率分别为 $p_1, p_2, \ldots , p_7$。换句话说，字母 $h$ 的概率是 $p_1$，字母 $e$ 的概率是 $p_2$，以此类推。保证 $p_i$ 的和等于 $1$。

最初，字符串 $S$ 的每个字符都是未知的。然后，SPY 将执行 $q$ 次操作，有两种类型：

• 类型 1：1 x c，表示 SPY 确定字符 $S_x$ 是 $c$。在本问题中，字符串 $S$ 的字符从 1 开始索引，因此 $S$ 可以表示为 $S_1S_2S_3\ldots S_n$。保证没有两个操作会相互冲突。
• 类型 2：2 l r，表示 SPY 想知道在子串 $S(l,r)$ 中，子序列等于 helloworld 的期望数量，结果对 $10^9 + 7$ 取模。这里，$S(l,r)$ 表示从索引 $l$ 开始到索引 $r$ 结束的子串（形式化地，$S_lS_{l+1}\ldots S_r$）。

在每次类型 2 的操作之后，你应该通过在新的一行输出期望值（对 $10^9 + 7$ 取模）来回答查询。

输入格式

输入包含多个测试用例。

输入的第一行包含一个整数 $t (1 \leq t \leq 10)$，表示测试用例的数量。

在每个测试用例中，接下来的几行提供详细信息：

第一行包含一个整数 $n (1 \leq n \leq 5 \times 10^4)$，表示字符串 $S$ 的长度。

第二行包含 7 个整数 $P_1, P_2, \ldots , P_7 (1 \leq P_i \leq 10^8)$。令 $P_t = P_1 + P_2 + \ldots + P_7$ 为这些值的总和。字母的概率定义为 $p_i = \frac{P_i}{P_t}$。

第三行包含一个整数 $q (1 \leq q \leq 5 \times 10^4)$，表示操作的数量。

接下来的 $q$ 行描述操作，每行指定操作的类型和参数。

保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^4$，$q$ 的总和不超过 $5 \times 10^4$。

输出格式

在每次类型 2 的操作之后，在新的一行输出期望值，对 $10^9 + 7$ 取模。

1
11
1 1 1 1 1 1 1
16
1 1 h
2 1 11
2 2 11
1 2 e
1 3 l
1 4 l
1 5 l
2 1 11
1 6 o
1 7 w
2 2 11
1 8 o
1 9 r
1 10 l
1 11 d
2 11 11

667718262
953066461
937670535
0
3