33481번 - 수열과 쿼리와 확률 3 서브태스크

문제

합동 세미나를 진행하던 중 유독 1학기 고급반 주제가 수열과 쿼리 혹은 트리와 쿼리를 연습문제로 하는 문제들 투성이였다. 재우가 1주차에 진행한 제곱근 분할법과 Mo’s, 진한이가 6주차에 진행한 HLD와 Dynamic Tree DP, 종우가 7주차와 8주차에 진행한 Segment Tree Beats, PST 모두 연습문제로 수열과 쿼리, 트리와 쿼리가 주어졌다. 동우는 이 기회에 진한이에게 물어보며 수열과 쿼리 시리즈를 풀기 시작했다.

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

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

• 1 $i$: $A_i$에 $A_i=A_i\times i$를 적용한다. (1ドル\le i\le N$)
• 2 $l$ $r$: 모든 $l\le i\le r$에 대해서 $A_i$에 $A_i=A_i\times i$을 적용한다. (1ドル\le l<r\le N$)
• 3 $l$ $r$: 모든 $l\le i\le r$에 대해서 모든 $A_i$에 $A_i=A_i\times l$을 적용한다. (1ドル\le l<r\le N$)
• 4 $l$ $r$: 모든 $l\le i\le r$에 대하여 $A_i=A_i\times r$을 적용한다. (1ドル\le l<r\le N$)

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

• 가능한 3ドル\binom{N}{2} +N$가지(1번 쿼리 $N$가지, 2, 3, 4번 쿼리 각각 $\binom{N}{2}$가지) 쿼리에 대해 동일한 확률로 하나의 쿼리를 적용한다. 이때, $N=1$이라면 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)$를 $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$의 배수가 아닌 경우만 주어짐이 보장된다.

제한

서브태스크

힌트