8971: Hello World 3 Pro Max

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 �1,�2,...,�7p1,p2,...,p7. In other words, there is a probability of �1p1 for the letter $h$, �2p2 for the letter $e$, and so on. It is guaranteed that sum of ��pi's is equal to 1.

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

• Type 1: $1xc$, which means SPY determines that the character ��Sx is $c$. In this problem, the characters in string $S$ are indexed starting from 1, so $S$ can be expressed as �1�2�3...��S1S2S3...Sn. It is guaranteed that no two operations will conflict with each other.
• Type 2: $2lr$, which means SPY wants to know the expected number of subsequences equals to $helloworld$ in the substring $S(l,r)$, modulo 109+7109+7. Here, $S(l,r)$ means the substring of $S$ starting at index $l$ and ending at index $r$ (formally ����+1...��SlSl+1...Sr).

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≤�≤5×104)(1≤n≤5×104), representing the length of string $S$.

The second line contains 7 integers �1,�2,...,�7P1,P2,...,P7(1≤��≤108)(1≤Pi≤108). Let ��=�1+�2+...+�7Pt=P1+P2+...+P7 be the sum of these values. The possibilities of the letters are defined as ��=����pi=PtPi.

The third line contains a single integer $q$(1≤�≤5×104)(1≤q≤5×104), 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×1045×104, sum of $q$ in all test cases will not exceed 5×1045×104.