ANIL_PRO - Anils Proposal

Anil is the best coder in his class. He is in love with his classmate Gowthami. One day he proposes her. She wants him to prove that his love is actually true. So, she poses the following problem:

There is an array of size n. Initially all the elements are zero. Now there will be two types of operations:

  • Update the array.
  • Query the array.

In case of update, you will be given a range [l, r]. To the kth element in this range (l and r inclusive), you need to add kth Fibonacci number.

In case of query, you will be given a range [l, r], for which you need to find the sum of all elements in the range (including l and r).

Anil hopes you can help him in this regard.

Input

The first line contains n (1 <= n <= 106) and q (1 <= q <= 5*104), the number of operations to be performed. The next q lines contain 3 space separated integers. If the first integer is 0, then it's an update operation. If it is 1, then it's a query operation. The next two integers specify l and r(1 <= l <= r <= n)

Output

For each query print one integer per line specifying the sum in the corresponding range. Since the sum can be very large, output Answer modulo 109 + 7.

Example

Input:
5 6
0 1 5
0 2 4
0 1 3
1 2 4
1 1 5
1 4 5

Output:
13
20
10

Explanation

After the first update the array looks as follows: 1 1 2 3 5

After 2nd update: 1 2 3 5 5

After 3rd update: 2 3 5 5 5

Hence from the above array, we have the outputs for the queries.

Note: Fibonacci Series starts as 1, 1, 2, 3, ...


Added by:nitish rao
Date:2014-03-09
Time limit:0.5s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:My own Problem

hide comments
2017-01-31 17:45:17
Repeatedly getting wrong answer for Test case 11
2014-07-28 20:31:23 AnilKumar
getting WA after 11th test case.
@nitish rao can you tell what i am missing
http://www.spoj.com/submit/ANIL_PRO/id=12039914

--nitish--> You are trying to store even large fibonacci numbers in int variable, thus causing over-flow.

Last edit: 2014-08-23 07:56:15
2014-03-10 12:56:59 Flago
@Abhishek Vijjapu
You should read as "Ans modulo(10^9+7)", not as "(Ans modulo 10^9)+7"
2014-03-09 23:52:31 Jacob Plachta
No, as usual, the answer should be calculated modulo (10^9+7).
2014-03-09 21:33:02 Abhishek Vijjapu
Answer should be modified as (answer%1000000000)+7. is that so ?
2014-03-09 14:46:25 Jacob Plachta
Cool problem!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.