Sasha and Array

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

Range-add the indices $a_i$; range-query the sum of Fibonacci values $f(a_i)$ modulo $10^9+7$.

Input

The first line contains $n,m$, followed by the array. Each query is 1 l r x (range add on indices) or 2 l r (query the Fibonacci-value sum).

Output

For each type-2 query print the answer modulo $10^9+7$.

Subtasks

• Subtask 1 (20%): size and operation count at most 30; all other validity conditions are unchanged.

• Subtask 2 (30%): size and operation count at most 3000; all other validity conditions are unchanged.

• Subtask 3 (50%): full constraints:

• $1\le n,m\le10^5$

• $1\le a_i,x\le10^9$

Examples

Input

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

Output

5
7
9

Explanation

The initial Fibonacci-value sum is 5. After adding 2 to indices [2,4], the index array becomes [1,3,4,3,1]; the following answers are 7 and 9.