MATKOR 문자열 만들기

재현이는 알파벳 대문자로만 이루어진 문자열 $S$를 하나 가지고 있다. 이 문자열 중 일부를 잘라 종우에게 선물을 주려고 한다. 종우는 선물 받은 문자열에 다음 과정을 통해 문자열을 MATKOR로 만들고 싶다.

• 선물 받은 문자열이 $A=a\_1a\_2a\_3\cdots a\_M$라고 하자.

• $a\_1$부터 $a\_M$까지 각 문자에 대해 아래 연산을 적용한다

  • 삭제 연산 : 문자열에서 해당 위치의 문자를 삭제한다.
  • 대체 연산 : 해당 위치의 알파벳을 다음 알파벳으로 바꾼다. 예를 들어 A는 B로, B는 C로 바꿀 수 있다. Z에는 이 연산을 적용할 수 없다.
  • 대체 연산의 경우 여러 번 적용할 수 있지만, 삭제 연산은 한 번만 적용할 수 있다.
  • 또한, 각 문자에 대해 최대 한 종류의 연산만 적용할 수 있다. 연산을 적용하지 않아도 된다.

• 연산을 모두 적용한 뒤 문자열을 MATKOR로 만들어야 한다.

재현이는 문자열 $S=s\_1s\_2s\_3\cdots s\_{\lvert S\rvert}$의 일부를 잘라 종우에게 선물해주려 한다. 재현이는 아래 쿼리에 대한 답을 알고자 한다. 아래 쿼리에서 $i$와 $j$는 $1$ 이상 $\lvert S\rvert$이하의 정수, $c$는 대문자 알파벳이다.

• $1$ $i$ $c$: $s\_i$를 $c$로 바꾼다.
• $2$ $i$ $j$: 재현이가 종우에게 $A=s\_is\_{i+1}\cdots s\_j$를 선물했을 때, 종우가 이 문자열을 MATKOR로 만드는 방법의 수와 각 방법당 총 연산 횟수의 분산을 구한다. 문자별로 적용된 연산의 종류와 횟수가 같다면 같은 방법이다.

이때 분산이란, 가능한 모든 서로 다른 연산 방법에 대한, 연산 사용 횟수에서 연산 사용 횟수의 평균을 뺀 값의 제곱의 평균을 의미한다. 조금 더 엄밀하게 말하자면 모든 가능한 연산 방법의 집합을 $T$, 연산 방법 $P$에서 연산을 사용한 횟수를 $|P|$라고 할 때 분산은 다음과 같이 계산할 수 있다.

$\frac{1}{\lvert T\rvert } \sum\_{P \in T} \left(\lvert P\rvert- \frac{1}{\lvert T \rvert} \sum\_{Q \in T} \lvert Q \rvert \right)^2$

첫 번째 줄에 대문자 알파벳으로 구성된 문자열 $S(6\le\lvert S\rvert\le 100\\, 000)$가 주어진다.

두 번째 줄에 쿼리의 수 $Q(1\le Q\le 100\\, 000)$가 주어진다.

세 번째 줄부터 $Q$줄에 걸쳐 다음 두 쿼리 중 하나가 주어진다. 쿼리 $2$는 적어도 한 번 이상 주어진다.

• $1$ $i$ $c$ ($1\le i \le\lvert S\rvert$; $c$는 대문자 알파벳)
• $2$ $i$ $j$ ($1\le i < i +5\le j \le\lvert S\rvert$)

쿼리 $2$가 주어질 때마다 쿼리의 답인 방법의 수와 분산을 한 줄에 공백으로 구분하여 출력한다.

단, 답이 매우 커질 수 있으므로 $10^9+7$으로 나눈 나머지를 출력한다. 또한 해당 쿼리의 방법의 수를 $10^9+7$으로 나눈 나머지가 $0$이라면 분산은 출력하지 않는다.

기약 분수 $\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$로 나눈 나머지가 $0$이 아니라면 분산이 정수 혹은 분모가 $10^9+7$의 배수가 아닌 유리수로 나타내어짐을 증명할 수 있다.