2600. 交错和查询

【题目描述】

无限循环数字串S由长度为n的循环节s构成。设s为12345(n=5)，则数字串S为123451234512345…

设Si为S的第i位数字，在上面的例子中，S1=1，S2=2，S6=1。

设S的一个子串S[l,r]的交错和为sum(l,r)：

sum(l,r) = Sl - S1+1 + Sl+2 - Sl+3 + … + (-1)r-lSr

如sum(2,7) = 2 - 3 + 4 - 5 + 1 - 2 = -3

现给定循环节s，要求支持两种操作：

1 pos digit：

修改循环节s上的某一位，即将spos改为digit。

2 l r：

求S[l,r]内所有子串的交错和的和，即

输出ans对109+7的模。

【输入格式】

第一行一个整数n，表示循环节s的长度。

第二行一个长度为n的数字串，表示循环节s。

第三行一个整数m，表示操作次数。

以下m行，每行3个整数。

若第一个数为1，表示是修改操作1 pos digit。

若第一个数为2，表示是询问操作2 l r。

【输出格式】

对于每个询问操作输出一行，表示答案。

【样例输入】

5

12345

5

2 1 5

2 6 10

1 3 5

2 1 5

2 1 6

【样例输出】

19

19

25

36

【数据范围】

对于10%的数据点，n, m <= 50；

对于20%的数据点，n, m <= 1000；

对于40%的数据点，1 <= l <= r <= n；

对于100%的数据点，n, m <= 200000；1 <= l <= r <= 1018；1 <= pos <= n；0 <= digit <= 9；