수열과 쿼리와 확률 1

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

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

• 1: 모든 $A\_i$에 대해 $A\_i=A\_i\times\frac{N+1-i}{N}$을 적용한다. 즉, $A\_1,A\_2,\cdots ,A\_N$에 각각 $\frac{N}{N} ,\frac{N-1}{N} ,\cdots ,\frac{1}{N}$을 곱한다.
• 2 $i$: $A\_i$에 $A\_i=A\_i\times i$를 적용한다. ($1\le i\le N$)

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

• 1번 쿼리와 2번 쿼리 중 어느 쪽을 적용할지 각각 $\frac{1}{2}$의 확률로 정한다.
  • 2번 쿼리를 정했다면, 가능한 $N$가지 쿼리 중 하나를 같은 확률로 정한다.
• 정한 쿼리를 적용한다.

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

• 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)$에 대해, $q$의 $M$에 대한 모듈로 곱셈 역원을 $q^{-1}$이라 하면 ($q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수) $M$으로 나눈 나머지는 $p\cdot q^{-1}\pmod M$로 정의한다. 정수인 경우에는 $q=q^{-1}=1$이므로 $p\pmod M$을 의미한다.

주어진 조건에서 기댓값이 정수 또는 유리수임을 증명할 수 있다. 유리수인 경우, 기약 분수의 분모가 $10^9+7$의 배수가 아닌 경우만 입력으로 주어진다.