MATKOR 문자열 만들기

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

선물 받은 문자열을 $A=a_1a_2a_3\cdots a_M$이라고 하자.

$a_1$부터 $a_M$까지 각 문자에 아래 연산을 적용한다.

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

연산을 모두 적용한 뒤 문자열이 MATKOR가 되어야 한다.

재현이는 아래 쿼리에 대한 답을 알고 싶다. 쿼리에서 $i$와 $j$는 1 이상 $|S|$ 이하의 정수이고, $c$는 대문자 알파벳이다.

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

여기서 분산은 가능한 모든 서로 다른 연산 방법에 대해, 방법별 연산 횟수에서 전체 평균을 뺀 값의 제곱의 평균이다. 가능한 모든 연산 방법의 집합을 $T$, 방법 $P$에서 사용한 연산 횟수를 $|P|$라고 하면 분산은 다음과 같다.

$\frac{1}{|T|} \sum_{P \in T} \left(|P| - \frac{1}{|T|} \sum_{Q \in T} |Q| \right)^2$

첫 번째 줄에 알파벳 대문자로 이루어진 문자열 $S$ ($6 \le |S| \le 100{,}000$)가 주어진다. 두 번째 줄에 쿼리의 수 $Q$ ($1 \le Q \le 100{,}000$)가 주어진다. 세 번째 줄부터 $Q$개의 줄에 다음 두 쿼리 중 하나가 주어진다. 쿼리 2는 적어도 한 번 이상 주어진다.

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

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

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

기약 분수 $\frac{p}{q}$ ($p \ge 0$, $q > 0$, $\gcd(p,q)=1$)를 $M$으로 나눈 나머지는 $q \cdot q^{-1} \equiv 1 \pmod M$을 만족하는 정수 $q^{-1}$을 사용하여 $p \cdot q^{-1} \bmod M$으로 정의한다. 정수인 경우 $q=q^{-1}=1$이므로 $p \bmod M$을 뜻한다.

방법의 수를 $10^9+7$로 나눈 나머지가 $0$이 아니라면, 분산은 정수이거나 분모가 $10^9+7$의 배수가 아닌 유리수로 나타낼 수 있음이 증명된다.