수열과 쿼리와 확률 2

동우는 수열과 쿼리 문제를 풀던 중, 왜 수열과 쿼리는 확률적으로 주어지지 않는지 궁금해졌다. 그래서 다음 문제를 만들었다.

길이가 $N$인 수열 $A=A_1,A_2,\cdots ,A_N$에 아래 연산 쿼리를 총 $M$번 적용하려고 한다.

• 1: 모든 $A_i$에 $N+1-i$를 곱한다. 즉, $A_1,A_2,\cdots ,A_N$에 각각 $N,N-1,\cdots ,1$을 곱한다.
• 2 $i$: $A_i$에 $i$를 곱한다. ($1\le i\le N$)

동우는 다음 규칙에 따라 $M$개의 쿼리를 각각 독립적으로 정한다.

• 1번 쿼리 1가지와 2번 쿼리 $N$가지, 총 $N+1$가지 쿼리 중 하나를 같은 확률로 골라 적용한다.

동우는 아래 두 질의 쿼리 중 하나를 실행하려고 한다.

• S: 초기 상태의 원소 합을 $S_0$, 최종 상태의 원소 합을 $S_1$이라 할 때, $\frac{S_1}{S_0}$의 값을 구한다.
• P: 초기 상태의 원소 곱을 $P_0$, 최종 상태의 원소 곱을 $P_1$이라 할 때, $\frac{P_1}{P_0}$의 값을 구한다.

그러나 성격이 급한 동우는 쿼리를 처리하기 전에 질의 쿼리 답의 기댓값을 알고 싶어졌다. 동우를 도와 구해 보자.

첫 번째 줄에 수열의 원소 개수 $N$($1\le N\le 10^6$)과 연산 쿼리의 개수 $M$($1\le M\le 10^{18}$)이 공백으로 구분되어 주어진다.

두 번째 줄에 초기 상태의 양의 정수 $A_1,A_2,\cdots ,A_N$($1\le A_i\le 10^9$)이 공백으로 구분되어 주어진다.

세 번째 줄에 동우가 묻고자 하는 질의 쿼리 문자 $Q$가 주어진다. $Q$는 S, P 중 하나이다.

첫 번째 줄에 질의 쿼리 답의 기댓값을 $10^9+7$로 나눈 나머지를 출력한다.

기약 분수 $\frac{p}{q}$($p\ge 0$, $q>0$, $\gcd(p,q)=1$)를 $10^9+7$로 나눈 나머지는 $q$의 모듈로 곱셈 역원 $q^{-1}$, 즉 $q\cdot q^{-1}\equiv 1\pmod{10^9+7}$을 만족하는 정수를 이용해 $p\cdot q^{-1}\pmod{10^9+7}$로 정의한다. 값이 정수이면 $q=q^{-1}=1$이므로 $p\pmod{10^9+7}$를 의미한다.

주어진 조건 내에서 기댓값은 정수 또는 유리수임을 증명할 수 있다. 유리수인 경우 기약 분수의 분모가 $10^9+7$의 배수가 아님이 보장된다.