题目描述

小糖原有好多好多个形如 $ax+b$ 的一次多项式（虽然初始时一个都没有），它们被排成了一行。

小糖原有一个幸运数字 $k$（可能是 npy 的生日日期哦！），而且小糖原会进行 $q$ 次操作！其中操作分为三种：

1. 在当前从左往右的第 $i$ 个一次多项式前插入一个新的一次多项式 $ax+b$（若 $i=n+1$ 则表示在最后插入）。
2. 翻转区间 $[l,r]$ 内的多项式。
3. 给定区间 $[l,r]$ 和自然数 $c$，查询 $[x^c](\prod\limits_{i=l}^r(a_ix+b_i)\bmod(x^k-1))$，即对 $\prod\limits_{i=l}^r(a_ix+b_i)$ 中满足 $t\equiv c\pmod k$ 的每个 $x^t$ 的系数求和，其中 $a_ix+b_i$ 表示当前从左往右的第 $i$ 个一次多项式。

因为小糖原迫切想要知道答案，所以本题强制在线！

为了防止答案过大，答案对 $10^9+7$ 取模。

输入格式

第一行，两个整数 $k,q$（$k\in\{2,7,14,18,20,21,22,25,26,27,30\}$，$1 \le q \le 2 \times10^5$）。

接下来 $q$ 行，每行若干个整数，形如：

• $1\;i'\;a'\;b'$；
• $2\;l'\;r'$；
• $3\;l'\;r'\;c'$；

含义见题目描述。

由于本题强制在线，记 $lst$ 为上次 $3$ 操作的答案（初始为 $0$），读入的 $i',a',b',l',r',c'$ 均需与 $lst$ 异或才能得到真实的 $i,a,b,j,l,r$（$1 \le i \le n+1$，$1 \le a,b \lt 10^9+7$，$1 \le l \le r \le n$，$0\leq c\lt k$，其中 $n$ 表示进行操作前一次多项式的数量）的值。

保证第 $2$、$3$ 类操作数总和不超过 $3\times 10^4$ 次。

输出格式

对于每个 $3$ 操作，输出一行一个整数表示答案。

样例

样例输入 1

2 7
1 1 2 9
1 2 9 1
1 1 2 1
2 2 3
3 1 2 1
1 8 14 9
3 8 15 11

样例输出 1

11
28

样例解释

对于第 $7$ 次操作，$\prod\limits_{i=l}^r(a_ix+b_i)$ 为 $(5x+2)(2x+9)$，即 $10x^2+49x+18$，满足 $t\equiv0\pmod 2$ 的 $x^t$ 项系数和为 $10+18=28$。