Problem Description

Once upon a time, Markyyz invented a problem named "Hello World".

Later, Markyyz invented a problem named "Hello World 2", which is a harder version of "Hello World".

Two thousand years later, SPY invented a problem named "Hello World 3", which is an even harder version of "Hello World".

Now, SPY is inventing a problem named "Hello World 3 Pro Max", which is ...

SPY has a string $S$ of length $n$ consisting of lowercase letters: $h,e,l,o,w,r,d$. The string is generated randomly in the following way: for each character in $S$, it is independently generated from the set $\{h,e,l,o,w,r,d\}$ with possibilities $p_1,p_2,...,p_7$. In other words, there is a probability of $p_1$ for the letter $h$, $p_2$ for the letter $e$, and so on. It is guaranteed that sum of $p_i$'s is equal to 1.

Initially, each character of string $S$ is unknown. Then, SPY will perform $q$ operations of two types:

• Type 1: $1\ x\ c$, which means SPY determines that the character $S_x$ is $c$. In this problem, the characters in string $S$ are indexed starting from 1, so $S$ can be expressed as $S_1S_2S_3...S_{n}$. It is guaranteed that no two operations will conflict with each other.
• Type 2: $2\ l\ r$, which means SPY wants to know the expected number of subsequences equals to $helloworld$ in the substring $S(l,r)$, modulo $10^9+7$. Here, $S(l,r)$ means the substring of $S$ starting at index $l$ and ending at index $r$ (formally $S_lS_{l+1}...S_r$).

After each operation of Type 2, you should answer the query by outputting the expected number on a separate line, modulo $10^9 + 7$.

Input

There are multiple tests.

The first line of input consists a single integer $t$$(1\le t\le 10)$, representing the number of test cases.

In each test case, the following lines provide the details:

The first line consists a single integer $n$$(1\le n\le 5\times10^4)$, representing the length of string $S$.

The second line contains 7 integers $P_1,P_2,...,P_7$$(1\le P_i\le 10^8)$. Let $P_t=P_1+P_2+...+P_7$ be the sum of these values. The possibilities of the letters are defined as $p_i=\frac{P_i}{P_t}$.

The third line contains a single integer $q$$(1\le q\le 5\times10^4)$, representing the number of operations.

The next $q$ lines describe the operations, each line specifying the type and parameters of the operation.

It is guaranteed that sum of $n$ in all test cases will not exceed $5\times10^4$, sum of $q$ in all test cases will not exceed $5\times10^4$.

Output

After every operation of Type 2, output the expected number on a single line, modulo $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 1 11

667718262
953066461
937670535
0
3