Hello everyone!!!

Hope everyone is safe and is doing well. I am honored to invite you to participate in HackerEarth July Circuits '20. It's a long contest that will start on July 18, 09:30 PM IST(check your timezone). This contest will run for 7 days.

This time, the problems were prepared by failed_coder, RestingRajarshi, chakred_namor, vivaan_gupta, krikti. Thanks to Arpa for testing the problems and helping us prepare the problems.

July Circuits’20 challenges you with 8 problems and the timeline is as follows:

• Day — 0 Problem 1, Problem 2, Problem 3
• Day — 1 Problem 4, Problem 5
• Day — 4 Problem 6, Problem 7
• Day — 6 Problem 8
• Day — 7 Challenge ends

New problem statements will be published every 48 hours, and yes, ace coders will win amazing vouchers.

This is a rated contest.

As usual, there will be some nice prizes for the top three competitors:

• First place: $100 Amazon gift card.
• Second place: $75 Amazon gift card.
• Third place: $50 Amazon gift card.

To know more about prizes check out this link.

Hope to see you at the scoreboard!

Good Luck & Have Fun.

https://codeforces.com/blog/entry/55597

Given an array of integers A1,A2,…,AN and the initial value of all elements are 0. Now you are given M queries, each belongs to one of three following types:

0 x y: Find the sum of all elements from index x to index y modulo 109+7

1 x y: Add 1×2×3 to Ax, add 2×3×4 to Ax+1, …, add (i+1)×(i+2)×(i+3) to Ax+iand so on until Ay

2 x y: Subtract 1×2×3 from Ax, subtract 2×3×4 from Ax+1, …, subtract (i+1)×(i+2)×(i+3) from Ax+i and so on until Ay

Input

The first line contains two integers N and M (1≤N,M≤10^5) — the size of the array and the number of queries, respectively.

Each of the next M lines containts three integers t x y denotes type and range of the query.

Output

For each query of type 0, print the required answer in a single line.

Sample testcase:

Input

8 4

1 1 8

0 2 8

2 4 6

0 5 6

Ouput

1974

462

Sample Clarification

In the example below:

After the first query, the array is [6,24,60,120,210,336,504,720]

The answer for the second query is 24+60+120+210+336+504+720=1974

After the third query, the array is [6,24,60,114,186,276,504,720]

The answer for the last query is 186+276=462

Hello everyone!!!

Hope everyone is safe and is doing well. I would like to invite you to participate in HackerEarth March Circuits '20. It's a long contest that will start on March 21, 21:00 IST(check your timezone). This contest will run for 7 days.

This time, the problems were prepared by failed_coder, Finding_Infinity, hackslash_123, krikti, Dalgerok and nikhil_c. Thanks to Arpa for testing the problems and helping us prepare the problems.

Copy-Paste Part :P

March Circuits’20 challenges you with 7 problems and the timeline is as follows:

• Day — 0 Problem 1, Problem 2 (Approximate)
• Day — 1 Problem 3, Problem 4
• Day — 4 Problem 5, Problem 6
• Day — 6 Problem 7
• Day — 7 Challenge ends

New problem statements will be published every 48 hours, and yes, ace coders will win amazing vouchers.

This is a rated contest with prizes for the top three coders.

To know more about prizes check out this link.