很久以前，Markyyz 发明了一个名为 "Hello World" 的问题。 后来，Markyyz 发明了 "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, \dots, p_7$。换句话说，字母 $h$ 的概率为 $p_1$，字母 $e$ 的概率为 $p_2$，以此类推。保证 $\sum p_i = 1$。

最初，字符串 $S$ 的每个字符都是未知的。随后，SPY 将执行 $q$ 次操作，操作分为两类： 类型 1：1 x c，表示 SPY 确定字符 $S_x$ 为 $c$。在本题中，字符串 $S$ 的字符下标从 1 开始，因此 $S$ 可以表示为 $S_1S_2S_3\dots S_n$。保证任意两次操作不会产生冲突。 类型 2：2 l r，表示 SPY 想知道在子串 $S(l, r)$ 中，子序列等于 helloworld 的期望数量，对 $10^9 + 7$ 取模。这里，$S(l, r)$ 表示从下标 $l$ 开始到下标 $r$ 结束的子串（形式上为 $S_l S_{l+1} \dots S_r$）。

在每次类型 2 的操作后，你需要输出该期望值，对 $10^9 + 7$ 取模。

输入格式

输入包含多组测试数据。 第一行包含一个整数 $t$ ($1 \le t \le 10$)，表示测试用例的数量。 对于每个测试用例，输入格式如下： 第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^4$)，表示字符串 $S$ 的长度。 第二行包含 7 个整数 $P_1, P_2, \dots, P_7$ ($1 \le P_i \le 10^8$)。令 $P_t = P_1 + P_2 + \dots + P_7$ 为这些值的总和。字母的概率定义为 $p_i = \frac{P_i}{P_t}$。 第三行包含一个整数 $q$ ($1 \le q \le 5 \times 10^4$)，表示操作次数。 接下来的 $q$ 行描述了操作，每行指定操作的类型和参数。 保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^4$，$q$ 的总和不超过 $5 \times 10^4$。

输出格式

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

样例

输入样例 1

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 1 11

输出样例 1

667718262
953066461
937670535
0
3