Fibonacci is back!!
Well, not alive but has been coming to Sheldon's dreams and has been giving him nightmares. Sheldon has asked him several times not to haunt him but Fibonacci says that he'll leave him only when he solves a problem.
The problems states that there are N integers arranged in an array Arr, initially all set to zero. There are Q queries, each being one of following two types--
1 i j a b - Increment elements of Arr from indices i to j(both inclusive) with a Fibonacci sequence having initial 2 terms as a and b respectively. Formally speaking, let the Fibonacci sequence be F0,F1,F2, ... with F0 being a and F1 being b. Now, we'll increment Arr[i] by F0, Arr[i + 1] by F1, Arr[i + 2] by F2, ... and Arr[j] by Fj−i.
2 i j - Output the sum of array elements from indices i to j(both inclusive) modulo 109+7. Formally, print (Arr[i] + Arr[i + 1] + .... + Arr[j]) % 109+7.
Note: Indexing is 1-based.
Input Format:
First line contains N and Q, length of array and number of queries respectively.
Each of the next Q lines with contain 5 integers and first integer will be 1 if the query is of type 1. It will start with 2 and will contain 3 integers if it is of type 2.
Output Format:
For each query of type 2, output the required answer in separate lines.
Constraints:
1≤N,Q≤105
1≤i,j≤N
1≤a≤b≤109
For 1st query, we add 1 to Arr[2] and 1 to Arr[3].
For 2nd query, sum % 109+7 is 1.
For 3rd query, we add 2 to Arr[1], 3 to Arr[2], 5 to Arr[3], 8 to Arr[4] and 13 to Arr[5].
For 4th query, we add 6 to Arr[5].
For 5th query, sum % 109+7 is 39.
Note: indexing is 1-based.