Chef and Magic Numbers

All submissions for this problem are available.
Chef is the cleverest man in the whole world. However he is not interested in science, give him the magic. His first magic lesson consists of converting a number k to F(k) where F(k)  is the kth magic integer. An integer is magic if S(n) is smaller than or equal to q. S(n) is the sum of squares of the digits in n. For example, S(13) = 1^2 + 3^2 = 10.
Now Chef want to test his magical abilities. He knows how to solve this task, but who will check it? That is where you come in.
The problem is as follows: there is an array of N numbers. Let A be the given array. Then Bi = F(Ai) for all i (1 <= i <= N). This is followed by M queries of the form (l, r). For each such query you need to find the sum of the elements of the array B that are in the interval (l, r) modulo 1000000007.
Input
The first line of the input contains an integer q. The next line contains an integer N. The third line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N} denoting the given array. Next line contains M denoting the number of queries. The next M lines contains two integers denoting left and right ends of queries.
Output
For each query, output a single line containing sum of the elements of the array B in the given interval.Constraints
 1 ≤ q ≤ 10^9
 1 ≤ N ≤ 3*10^5
 1 ≤ Ai ≤ 3*10^5
 1 ≤ M ≤ 10^5
 1 ≤ l ≤ r ≤ N
Example
Input: 201 5 1 2 10 5 10000 5 1 1 2 2 3 3 5 5 1 5 Output: 1 2 10 10636 10654
Scoring
Subtask 1 (30 points): 200 ≤ q ≤ 10^{9}.Subtask 2 (70 points): Look at constraints
Author:  furko 
Tester:  balajiganapath 
Editorial  http://discuss.codechef.com/problems/CHMAGIC 
Tags  adhoc, furko, ltime04, medium 
Date Added:  5082013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 