Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 3772
Calculate the Function

Time Limit: 2 Seconds      Memory Limit: 65536 KB

You are given a list of numbers A1 A2 .. AN and M queries. For the i-th query:

• The query has two parameters Li and Ri.
• The query will define a function Fi(x) on the domain [Li, Ri]Z.
• Fi(Li) = ALi
• Fi(Li + 1) = A(Li + 1)
• for all x >= Li + 2, Fi(x) = Fi(x - 1) + Fi(x - 2) × Ax

You task is to calculate Fi(Ri) for each query. Because the answer can be very large, you should output the remainder of the answer divided by 1000000007.

#### Input

There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:

The first line contains two integers N, M (1 <= N, M <= 100000). The second line contains N integers A1 A2 .. AN (1 <= Ai <= 1000000000).

The next M lines, each line is a query with two integer parameters Li, Ri (1 <= Li <= Ri <= N).

#### Output

For each test case, output the remainder of the answer divided by 1000000007.

```1
4 7
1 2 3 4
1 1
1 2
1 3
1 4
2 4
3 4
4 4
```

#### Sample Output

```1
2
5
13
11
4
4
```

Author: CHEN, Weijie
Source: The 14th Zhejiang University Programming Contest
Submit    Status