情书
题号：NC21366
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述 

——当你收到情书，也代表我已经走远。

小A最近看上了一个女生，非常激动地想给她写情书。情书是只由小写英文字母构成的字符串。由于女生的心思非常难猜，她们总是会随机挑选情书的某一段来读，从而判断男生的诚意是否足够。女生会通过情书的内容，以及自身的心动程度来对情书产生心动值。
现在小A已经写好了一份情书，但毕竟这可是他第一次写情书，可要好好斟酌一番。现在他想知道，如果他把情书中的一段送给心爱的女生，能够收获心动值的期望是多少。如果期望的心动值太低的话，他会继续修改他的情书的。

具体来说，若女生的心动程度为 b ，则女生的心动值可以看做情书在 b 进制意义下的数。即 s[i]=s[i-1]*b+(a[i]-'a'+1) 。其中 a[i] 为情书中的字符，s[0]=0，s[len] 即为该情书的心动值。

有两种操作，第一种为询问情书的一个子串，即如果女生随机在该子串内随机选择一个子串，心动值的期望为多少。第二种为把情书的某一个字符修改为另一个字符。

输入描述:

第一行三个整数 n,m,b，分别表示情书长度、询问个数以及女生的心动程度。
接下来一行一个长为 n 的字符串表示情书。接下来 m 行，每行先是一个 0 或 1 的整数 opt。
如果 opt=0， 接下来两个整数 l,r,(1≤l≤r≤n)，表示对子串 [l,r] 进行询问。
如果 opt=1 ，接下来一个整数 x 和一个字符 c ，表示把 x 位置上的字符修改为 c 。

输出描述:

对于每个询问，输出一行一个值表示答案。答案对 1000000007 取模。
示例1

输入

复制 
3 3 10
abc
0 1 3
1 2 c
0 1 2

输出

复制 
333333363
666666677

说明

第一个询问中，修改之前有 a,b,c,ab,bc,abc 六种选法，心动值分别为 1,2,3,12,23,123，总和为 164 ，所以输出\frac{164}{6}(mod1000000007)=333333363 。
示例2

输入

复制 
14 1 99
iloveyousomuch
0 1 14

输出

复制 
336269480

备注:

对于 20%的数据，n,m≤100
对于 40%的数据，n,m≤3000
对于额外 20%的数据，opt=0
对于 100%的数据，n,m≤200000,1<b≤109
由于小A长相帅气，女生的心动程度不会很小（与解题并没有关系）。