You are given an array A(1-based index) consisting of N integers. You have to process two types of queries on this array.

Type 1: Given ID and VAL, perform the operation UPDATE(ID, VAL)

    UPDATE(ID, VAL):

        if VAL == 0:

            return

        A_ID = A_ID + VAL

        if ID == N:

            UPDATE(1, VAL - 1)

        else :

            UPDATE(ID + 1, VAL - 1)

Type 2: Given L and R, find QUERY(L, R)

    QUERY(L, R):

        if L == R:

            return A_L

        if L == N:

            return A_L + QUERY(1, R) 

        else :

            return A_L + QUERY(L + 1, R)

Input:

• The first line of input contains two space separated integer N and Q denoting size of array and number of queries respectively.
• The second line contains N space separated integers denoting array A.
• Next Q lines are of one of the following format:
  • 1 ID VAL : for type 1 query
  • 2 L R : for type 2 query

Output:

• For each type 2 query, output the answer modulo 10⁹+7 in a new line.

Constraints:

• $1 \le N,Q \le 10^{5}$
• $1 \le L,R \le N$
• $1 \le VAL \le 10^{9}$