Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Fybonačis

Jau turbūt yra tekę ne kartą susidurti su Fibonačio skaičių seka. Kaip žinia, tai yra seka, kurios pirmi du nariai yra F_1=F_2=1, o kiekvienas kitas narys apskaičiuojamas pagal taisyklę F_n=F_{n-1}+F_{n-2}.

Šiame uždavinyje nagrinėjama kita seka, kurią pavadinsime \\varphi-bonačio seka. Jos nariai apibrėžiami taip:

  • F_i=x_i, jei 1\\leqi\\leq\\varphi;
  • F_i=F_{i-1}+F_{i-2}+...+F_{i-\\varphi}, jei \\varphi<i.

Galima pastebėti, kad jau aptarta Fibonačio seka yra tiesiog atskiras \\varphi-bonačio sekos atvejis, kuomet \\varphi=2 bei x_1=x_2=1.

Jūsų užduotis - surasti n-ąjį duotos \\varphi-bonačio sekos narį.

Pradinai duomenys

Pirmoje eilutėje pateikti du tarpu atskirti sveikieji skaičiai \\varphi ir n (1\\leq\\varphi,n\\leq2\\cdotp10^5).

Antroje eilutėje pateikta \\varphi tarpais atskirtų sveikųjų skaičių x_1,x_2,...,x_{\\varphi} (1\\leqx_i\\leq10^9).

Rezultatai

Jūsų programa turi išvesti vieną sveikąjį skaičių F_n - n-ąjį apibrėžtos \\varphi-bonačio sekos narį. Kadangi skaičiai gali būti labai dideli, išveskite rezultatą moduliu 10^9+7.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
2 10
1 1
 
55
 
3 4
1000000000 1000000000 1000000000
 
999999986
 
4 2
1 2 3 4
 
2

Paaiškinimas

Pirmajame pavyzdyje apibrėžta įprastinė Fibonačio seka, kurios dešimtasis narys yra lygus 55.

Antrajame pavyzdyje ketvirtojo sekos nario reikšmė yra 1000000000+1000000000+1000000000=3000000000, tačiau atsakymą reikia išvesti moduliu 10^9+7, tad teisingas atsakymas yra 3000000000\\mod1000000007=999999986.

Trečiajame pavyzdyje tereikia išvesti antrąjį sekos narį, kuris jau duotas ir yra lygus 2.