Definim recursiv următorul șir: x[0]=x0, x[1]=x1, x[i]=a∙x[i-1]+b∙x[i-2]+c, pentru orice i≥2.
Cerinţă
Realizați un program care calculează suma x[s]+x[s+1]+...+x[f]. Deoarece această sumă poate fi foarte mare se cere afișarea acesteia modulo 101587009.
Date de intrare
Pe prima linie a fișierului de intrare sir9.in se găseşte numărul natural T, reprezentând numărul de instanţe ale problemei ce trebuiesc rezolvate. Următoarele T linii conţin descrierea celor T instanţe. Mai exact, pe linia i+1 se găsesc numerele naturale x0, x1, a, b, c, s şi f reprezentând datele pentru instanţa i.
Date de ieşire
Fișierul de ieșire sir9.out va conține T linii. Pe linia i se va afla răspunsul pentru instanţa i.
Restricţii
1≤T≤1000 0≤x0, x1, a, b, c≤108 0≤s≤f≤1018
Pentru teste în valoare de 20 puncte, suma valorilor lui f pentru cele T instanţe nu va depăşi 107.
Exemple
sir9.in
sir9.out
Explicaţii
2
0 1 1 1 0 3 5
2 1 2 1 3 0 4
10
74
Sunt două instanțe. Pentru prima instanţă, şirul x este 0, 1, 1, 2, 3, 5, ..., deci suma cerută este 2+3+5=10. Pentru a doua instanţă, şirul x este 2, 1, 7, 18, 46, ..., deci suma cerută este 2+1+7+18+46=74.