33470번 - 수열과 쿼리와 확률 2 서브태스크

문제

동우는 수열과 쿼리 시리즈를 풀다가 왜 수열과 쿼리가 확률적으로 주어지지 않는지 의문이 들었다. 이에 다음 문제를 만들었다.

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

• 1: 모든 $A_i$에 대해 $A_i=A_i\times\left( {N+1-i} \right)$를 적용한다. 즉, $A_1,A_2,\cdots ,A_N$에 각각 $N,N-1,\cdots ,1$을 곱한다.
• 2 $i$: $A_i$에 $A_i=A_i\times i$를 적용한다. (1ドル\le i\le N$)

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

• 가능한 $N+1$가지(1번 쿼리 1ドル$가지, 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$의 배수가 아닌 경우만 주어짐이 보장된다.

제한

서브태스크

힌트