Edward Elric has learnt new Alchemy technique, if he uses this technique on 1x1 block with power f[i] then height on this block increases by f[i],also his power in ith move depends on powers of his previous three moves i.e.
f[i] = x*f[i-1] + y*f[i-2] + z*f[i-3] here x,y,z are some constant and if he uses technique for first, second, third time then his power will be f1,f2,f3.
To test Edward's power Colonel Mustang gives him arena of dimension 1xN and gives him Q queries in each query Mustang gives him two integers L and R i.e. he has to perform his new technique on each block from L to R, but Alex Louis Armstrong orders Edwards to perform in reverse on for each query i.e. first perform on R then R-1,R-2,....L . In each query he cant skip any block, and after each operation he takes 2 min break, so that in next query he has to start again.
His brother Alphonse Elric is nervous about how his brother will perform and he cant wait for results so he is asking for your help
- The first line of the input contains an integer T denoting the number of test cases . The description of T testcases follow.
- First line of each test case contains three space seperated integers x,y,z ( constants for f[i] = x*f[i-1] + y*f[i-2] + z*f[i-3] )
- Second line of each test case contains three space seperated integers f1,f2,f3 ( Edward’s initial power )
- Next line contiains an Integer N denoting Dimension of arena .
- Next line contiains an Integer Q denoting number of Queries .
- Next Q line contains two space seperated integers L,R denoting range for ith query
For each test case print Arena i.e size of each block modulo (1000000007)
- 1 ≤ T ≤ 20
- -100000 ≤ x , y , z ≤ 100000
- -100000 ≤ f1, f2 , f3 ≤ 100000
- 1 ≤ N ≤ 10000
- 1 ≤ Q ≤ 100000
- 1 ≤ L ≤ R ≤ N
1 2 3
4 5 6
34 11 9 4 0
initial arena :- 0 0 0 0 0
arena after first query :- 6 5 4 0 0
arena after second query :- 34 11 9 4 0
According to given equation f=4 f=5 f=6 ; f=1*6 + 2*5 + 3*4=28
So in first query of 1 to 3 a+=f, a+=f, a+=f
In second query 1 to 4 a+=f, a+=f, a+=f, a+=f
Hence the answer.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions