Xiao Tangyuan originally has many linear polynomials of the form $ax+b$ (though initially, there are none), which are arranged in a row.

Xiao Tangyuan has a lucky number $k$ (which might be their partner's birthday!), and Xiao Tangyuan will perform $q$ operations. There are three types of operations:

1. Insert a new linear polynomial $ax+b$ before the $i$-th linear polynomial from the left (if $i=n+1$, it means inserting at the end).
2. Reverse the polynomials in the range $[l, r]$.
3. Given a range $[l, r]$ and a natural number $c$, query $[x^c](\prod\limits_{i=l}^r(a_ix+b_i) \bmod (x^k-1))$, which is the sum of the coefficients of $x^t$ for all $t \equiv c \pmod k$ in the product $\prod\limits_{i=l}^r(a_ix+b_i)$, where $a_ix+b_i$ denotes the $i$-th linear polynomial from the left.

Because Xiao Tangyuan urgently wants to know the answer, this problem is forced to be online!

To prevent the answer from being too large, the answer is taken modulo $10^9+7$.

Input

The first line contains two integers $k, q$ ($k \in \{2, 7, 14, 18, 20, 21, 22, 25, 26, 27, 30\}$, $1 \le q \le 2 \times 10^5$).

The next $q$ lines each contain several integers, in one of the following formats:

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

The meanings are as described in the problem description.

Since this problem is forced to be online, let $lst$ be the answer to the last type 3 operation (initially $0$). The input values $i', a', b', l', r', c'$ must be XORed with $lst$ to obtain the actual values $i, a, b, l, r, c$ ($1 \le i \le n+1$, $1 \le a, b < 10^9+7$, $1 \le l \le r \le n$, $0 \le c < k$, where $n$ is the number of polynomials before the operation).

It is guaranteed that the total number of type 2 and type 3 operations does not exceed $3 \times 10^4$.

Output

For each type 3 operation, output one integer per line representing the answer.

Examples

Input 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

Output 1

11
28

Note

For the 7th operation, $\prod\limits_{i=l}^r(a_ix+b_i)$ is $(5x+2)(2x+9)$, which is $10x^2+49x+18$. The sum of the coefficients of $x^t$ where $t \equiv 0 \pmod 2$ is $10+18=28$.