수열과 쿼리와 확률 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)$를 $M$으로 나눈 나머지는 $q^{-1}$가 $q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원일 때, $p\cdot q^{-1}\pmod M$로 정의한다. 만약 정수일 경우 $q=q^{-1}=1$이므로 $p\pmod M$를 의미한다.

주어진 조건 내에서 기댓값이 정수 혹은 유리수임을 증명할 수 있으며, 유리수의 경우 기약분수에서 분모가 $10^9+7$의 배수가 아닌 경우만 주어짐이 보장된다.