You are given an array A consisting of N integers. You have to process two types of queries on this array.
Type 1: Change the ith element to X
Type 2: Given l and r, calculate: $\sum_{i=l}^{r} \sum_{j=i}^{r} Fib ( \sum_{k=i}^{j} A_k )$

Note: $Fib(i)$ is the ith Fibonacci number. $Fib(0)=0 \space.\space Fib(1)=1$

Input

First line contains an integer N.
Next line contains N space separated integers denoting array A.
Next line contains the integer Q.
Next Q lines are of the following format:
$1 \space i \space X$ : for type 1 query
$2 \space l \space r$ : for type 2 query

Output

For each type 2 query output the answer modulo $10^9+7$ on a new line.

Constraints

$1 ≤ N,Q ≤ 10^5$
$1 ≤ A[i],x ≤ 10^9$
$1 ≤ l,r,i ≤ N$
$l ≤ r$