Function F is defined as F=0 F=1 F[n]=F[n-1]+F[n-2] for every other n
Function S[i][j] = summation(F[x]) i<=x<=j
You have to output S[i][j]%(109+7) for given i,j
You have T test cases.
Each test case starts with N and Q. N being index of biggest fibonacci number for that test case and Q being number of queries.
Next Q lines contains two integer i,j (0<= i,j <=N)
For each query (i,j) ,print S[i][j] modulo (109+7) in a new line.