Sequences, Queries, and Probability 3

While running a joint seminar, we noticed that most of the advanced class topics in Semester 1 were problems built around sequence and query or tree and query exercises. Jaewoo covered sqrt decomposition and Mo's algorithm in Week 1, Jinhan covered HLD and dynamic tree DP in Week 6, and Jongwoo covered Segment Tree Beats and PST in Weeks 7 and 8. All of them were given sequence and query or tree and query problems as exercises. Dongwoo took this chance to ask Jinhan questions and started solving the sequence and query series.

While working through the series, Dongwoo wondered why sequence and query problems are never given with probabilities. So he made the following problem.

Dongwoo wants to apply the operation queries below a total of $M$ times to a sequence $A=A_1,A_2,\cdots,A_N$ of length $N$.

• 1 $i$: Applies $A_i=A_i\times i$ to $A_i$. ($1\le i\le N$)
• 2 $l$ $r$: Applies $A_i=A_i\times i$ to $A_i$ for every $l\le i\le r$. ($1\le l<r\le N$)
• 3 $l$ $r$: Applies $A_i=A_i\times l$ to every $A_i$ for every $l\le i\le r$. ($1\le l<r\le N$)
• 4 $l$ $r$: Applies $A_i=A_i\times r$ for every $l\le i\le r$. ($1\le l<r\le N$)

Dongwoo decides each of the $M$ queries independently by the following rule.

• Out of the $3\binom{N}{2}+N$ possible queries (N of type 1, and $\binom{N}{2}$ each of types 2, 3, and 4), one query is applied with equal probability. Note that if $N=1$, the type 1 query always applies.

Dongwoo wants to run one of the two question queries below.

• S: Let $S_0$ be the sum of the elements in the initial state and $S_1$ the sum in the final state. Find the value of $\frac{S_1}{S_0}$.
• P: Let $P_0$ be the product of the elements in the initial state and $P_1$ the product in the final state. Find the value of $\frac{P_1}{P_0}$.

Impatient Dongwoo wants to know the expected value of the answer to the question query before processing any queries. Help Dongwoo find it.

The first line contains the number of elements $N(1\le N\le 10^6)$ and the number of operation queries $M(1\le M\le 10^{18})$, separated by a space.

The second line contains the sequence $A_1,A_2,\cdots,A_N(1\le A_i\le 10^9)$ in its initial state, which consists of positive integers separated by spaces.

The third line contains the question query character $Q$ that Dongwoo asked about. $Q$ is either S or P.

Print the expected value of the answer to the question query modulo $10^9+7$ on the first line.

For an irreducible fraction $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q)=1)$, its value modulo $10^9+7$ is defined as $p\cdot q^{-1}\pmod{10^9+7}$, where $q^{-1}$ is the integer satisfying $q\cdot q^{-1}\equiv 1\pmod{10^9+7}$, that is, the multiplicative inverse of $q$ modulo $10^9+7$. If the value is an integer, then $q=q^{-1}=1$, so the result is $p\pmod{10^9+7}$.

Under the given conditions, the expected value can be proven to be an integer or a rational number. For a rational number, the denominator of the irreducible fraction is guaranteed not to be a multiple of $10^9+7$.