Mr. Gora's assignments are shitty. So i will try to make this problem statement asap (as shitty as possible). :P

Mr. Gora decided to conduct a test. He hates copying so he decided to arrange students in such a way so that copying is minimal. Though there are 3 columns in each class he will allow the students to sit only in middle column. There are N tables in this column and in each table 3 students can sit. Now in his view there are N X 3 empty places in a N X 3 matrix. He assumes that if either many boys or many girls are together then there will be lot of copying. So he won't allow these kind of placing:

1. 3 boys should not sit on a single bench, i.e. there shouldn't be a matrix of size 1 X 3 filled with boys.

2. 3 girls should not sit on a single bench, i.e. there shouldn't be a matrix of size 1 X 3 filled with girls.

3. There shouldn't be any 2 X 2 matrix filled only with boys.

4. There shouldn't be any 2 X 2 matrix filled only with girls.

Now he wonders in how many ways can he arrange his students for a given value of N assuming there are infinite number of boys and girls in the campus. He calls this number of ways as Gora's number.

Your task in not just finding this Gora's number for a given value of N. I told you that the problem statement will be asap. xD

You are given a Gora array of size S. Gora array consists of some random numbers. You need to perform Q(will be given) queries on this array.
There are two types of queries.
1 L R X - Increment values in the range L to R by X.
2 L R - output the sum of values of Gora number(Gora array[i]) where i ranges from L to R. As this sum can be very large and Gora can't handle large numbers print sum modulo 10⁹+7.

Constraints:

1<=S<=10⁵
1<=Q<=10⁴
1<=Gora array[i]<=10⁹
1<=L<=R<=S
1<=X<=10⁹

Input:

First line contains two integers S and Q.
Second line contains S space separated integers denoting numbers in Gora array.
Next Q lines contains queries which may be of type1 or type2.
Type 1 query format:
1 L R X
Type 2 query format:
2 L R

Output:

Print the required answer for each query of type 2.

Note: No place should be left empty.

Problem Setter - Teja Vojjala