You are given an array A of size n. You are also given q queries where each query is described by two values, start and jump.

For each query you will perform the following operations:

Set SUM 0.

Begin at the index i=start and add the element A[i] to the value of SUM.

Set i=i + jump and add Arr (i+jump) to SUM till i + jump <= N.

The answer to each query is the value of SUM after performing the above operations. Find the sum of answers to all q queries. Since the output can be large return it modulo 10 power 9 +7.

The first line of input contains two space separated integers n (1≤n≤105) and q (1≤q≤105) — the number of elements in the array A and the number of queries respectively..

The second line of input contains n space separated integers A0,A1,...An−1 (1≤Ai≤109) — the elements of array A respectively.

The next q lines contain two space separated integers start (0≤start≤n−1) and jump (1≤jump≤n) denoting the queries.