Description

有一个 $n\times n$ 的矩阵 $A$，下标从 $A_{1,1}$ 至 $A_{n,n}$，初始时所有元素的值都为 $1$。

有 $q$ 次操作，每次有两种类型。

1. 给定 $x,v$，表示对于所有 $1\le i\le x,1\le j\le n-x+1$，将 $A_{i,j}$ 乘以 $v$。

2. 给定 $x1,y1,x2,y2$，求 $\sum\limits_{i=x1}^{x2}\sum\limits_{j=y1}^{y2}A_{i,j}$。

答案对 $10^9$ 取模。

Format

Input

第一行两个数 $n,q$。

接下来 $q$，每行两种输入格式。

1. $1\ x\ v$，表示操作一。

2. $2\ x1\ y1\ x2\ y2$，表示操作二。

Output

对于每个操作二，一行一个答案。

Samples

3 3
1 2 2
1 3 3
2 1 1 2 3

18

Limitation

$n,q\le10^6$

$1\le x\le n,v\lt10^9$

$1\le x1\le x2\le n,1\le y1\le y2\le n$