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$.

There are multiple tests.

The first line of input consists a single integer $t(1≤t≤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≤n≤5×10^4)$, representing the length of string $S$.

The second line contains $7$ integers $P_1,P_2,...,P_7(1≤P_i≤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≤q≤5×10^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×10^4$, sum of $q$ in all test cases will not exceed $5×10^4$.

After every operation of Type 2, output the expected number on a single line, modulo $10^9+7$.