题目描述

现在有一个二维矩阵 $a$，初值是杨辉三角，不在三角形内的则为 $0$。如，下面是这个矩阵的前 $5$ 行：

 1 0 0 0 0
 1 1 0 0 0
 1 2 1 0 0
 1 3 3 1 0
 1 4 6 4 1

注意，如第 $4$ 行 1 3 3 1 0，后面并不是没有数了，而是有无穷多个 $0$。

这个矩阵支持两种操作：

• 1 x y，表示把 $a_{x,y}$ 加上 $1$。

• 2 x y，表示求第 $x$ 行到第 $y$ 行的和 $\bmod (10^9+7)$。$x\le y$。

输入格式

本题强制在线。

第一行一个整数 $m$ ，表示共有 $m$ 个操作。所有的 $x$ 和 $y$ 均为整数。

下面 $m$ 行，每行三个整数 $\text{opt},x',y'$，$\text{opt}$ 代表操作的序号（$1\le \text{opt} \le 2$），$x'$ 和 $y'$ 表示加密后的操作数。

记上一次 $2$ 操作的答案为 $\text{ans}$，则每次操作的 $x'$ 和 $y'$ 都要异或上 $\text{ans}$ 才是真实的 $x$ 和 $y$。初始 $\text{ans}$ 为 $0$。

输出格式

对于所有的 $2,3$ 操作，每行输出一个答案。

样例

输入

3
1 1 2
2 1 3
1 9 9

输出

8

说明

【数据范围】

对于 $10\%$ 的数据，$1 \le m,x,y \le 10$。

对于 $40\%$ 的数据，$1 \le x,y \le 10^5$，$m\le 10^4$。

对于 $100\%$ 的数据，$1 \le x,y \le 10^9$，$1\le m\le 5 \times 10^5$。

【样例说明】

加密前的输入数据：

3
1 1 2
2 1 3
1 1 1

初始矩阵：

 1 0 0
 1 1 0
 1 2 1

第 $1$ 个操作后的矩阵：

 1 1 0
 1 1 0
 1 2 1

第 $2$ 个操作的答案：$(1+1+0)+(1+1+0)+(1+2+1)=8$。

第 $3$ 个操作后的矩阵：

 2 1 0
 1 1 0
 1 2 1