QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 64 MB Total points: 100 Hackable ✓
[0]

# 4260. 胡策的数列

Statistics

在 OI 界,有一个无人不知无人不晓,OI 水平前无古人后无来者的胡策,江湖人称一眼秒题胡大爷!

今天胡策正在研究一个远古传下来的数列:a0,a1,a2,,数列的第 k 项为 ak。这个数列有特别的性质,对于 i>1 有:25ai+20ai1=12ai2。因为流传的时间太过久远,a0a1 的值都已经看不清了,但是在最后还记载着,这个数列有一个特别的性质:对于任意的 i0,都有 ai0

然而胡策已经看穿了一切:对于任意一个正数 t,满足 a0=t 的数列 a 是唯一的!但是,他想拿这个问题考一考拜胡策为师的你。

具体来说,胡策会给你一个长度为 n 的表格,一开始每个格子都写着 0。有时他会让你将 a0=t 时的数列 a 从第 p 项到第 p+rl 项的值分别写入表格中第 l 到第 r 格(覆盖原有的值),有时他会询问表格中某一段连续的格子中的数的和。

当然,作为胡策的弟子,你必须在胡策提出一个询问的时候马上作出回应。

因为这是一个远古的问题,胡策只给了你一台远古的计算机,它只有 64MB的内存。

输入格式

第一行两个正整数 n,m。分别表示表格的长度和操作个数。

接下来 m 行,每行描述一个操作。每行的第一个整数 type 描述了操作的类型,type=1 表示是修改操作,type=2 表示是询问操作。

如果是修改操作,接下来有四个整数 l,r,t,p,意义如上所述。

如果是询问操作,接下来有两个整数 l,r,意义如上所述。

由于胡策需要确定你是在线回答他的问题,输入中的 l,r 是加密了的。于是你需要把输入中的 l,r 分别异或 lastans 来得到实际的 l,rlastans 表示上一次询问操作的答案,初始为 0。保证实际的 l,r 满足 1lrn

输出格式

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

答案一定能写成 vu 的形式,其中 v,u 是互质的整数,且 u>0。为了避免分数,你只用输出一个介于 0109+8 之间的整数 x 满足 ux \equiv v \pmod{10^9 + 9} 来表示答案。显然在本题中,这样的 x 是唯一的。

样例一

input

3 3
1 1 3 2 3
1 2 2 4 5
2 1 3


output

867840008


explanation

答案是 \frac{592}{3125},对应的 x867840008

样例二

input

1000000000 3
1 1 12450 6666666 23333333
1 6666 99999 2333 44444
2 1 1000000000


output

431287288


样例三

见样例数据下载。

限制与约定

对于 20% 的数据,n,m \leq 1000

对于 50% 的数据,n,m \leq 30000

对于 100% 的数据,1 \leq n \leq 10^91 \leq m \leq 10^51 \leq t \leq 10^91 \leq p \leq 10^9

时间限制:1\texttt{s}

空间限制:64\texttt{MB}

来源

中国国家集训队互测2015 - By 张天扬