暂无测试数据。

有一天蒜头君在攻略一款游戏时，发现这款游戏有一个可怕的无限循环。

如果要逃出这个循环，便需要回答 $n$ 个问题。

这些问题的选项数量十分特殊。每个问题的选项数量与问题本身无关，而是和这个问题是第几个被回答的有关。

形式化的说法，如果当前还有 $i$ 个问题需要被回答，那么游戏将为这个问题提供 $c_i$ 个选项。

蒜头君发现这个游戏还有一些神奇的特性：

• 如果当前还有 $i$ 个问题需要回答，如果回答正确，则继续回答下一个问题;
• 而如果回答错误，则游戏会删除剩下的 $i$ 个问题，然后从区间 $[i,n]$ 随机生成一个需要回答问题的数量 $size$ ，重新生成 $size$ 个问题并打乱答案，让蒜头君继续回答。

由于蒜头君快进了不少剧情，他当然是不知道这些问题的正确答案的。 于是他写了一个程序来回答问题，也就是每次无脑选择第一个选项! 他想知道从开始（剩余 $n$ 个问题）到剩余 $q$ 个问题的状态，这个程序期望进行多少次选择。当然这个数字不一定是个整数，但肯定是个有理数 $x/y$（最简分数），所以请告诉蒜头君该数字在模 $1,000,000,009$ 意义下的值，也即 $x y^{-1} \bmod 1,000,000,009$，其中 $y^{-1}$ 为 $y$ 在模 $1,000,000,009$ 意义下的逆元。

由于蒜头君的程序存在未知 Bug ，有时候会造成游戏的 $c_i$ 值修改。对于每次修改，你需要回答修改后询问的值。

输入格式

第一行两个整数 $n, m$ ，表示总问题数和蒜头君的操作次数。

第二行 $n$ 个整数 $c_1 - c_n$ ，表示初始状态的选项数目。 接下来 $m$ 行，每行一个整数 $o$ ，表示操作类型。

如果 $o = 1$ ，表示这是一个询问操作，接下来一个整数 $q$ ，表示询问从开始（剩余 $n$ 个问题）到剩余 $q$ 个问题的状态，这个程序期望进行多少次选择。

如果 $o = 2$ ，接下来两个整数 $p,x$ 表示蒜头君的程序出现 Bug，将 $c_p$ 修改为 $x$ 。

输出格式

对于每个询问操作，输出一行一个整数 $ans_i$ ，表示询问的答案。

数据范围

3 3
1 4 4
1 2
1 1
1 3

4
14
0

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

0
9
4

10 10
1 5 4 5 3 3 3 1 1 4
1 5
2 5 4
2 3 2
1 2
1 1
2 10 4
1 7
1 8
1 6
2 6 1

100000033
296429348
740876293
6
5
500000018