h2. Cerinţă

Kokalaru47 vă roagă să-i spuneţi care este numărul maxim de scheme de papagali ce pot fi efectuate în situaţia iniţială şi în fiecare dintre planurile sale, modulo $1 000 000 007$.

Kokalaru47 vă roagă să-i spuneţi care este numărul maxim de scheme de papagali ce pot fi efectuate în situaţia iniţială şi în fiecare dintre planurile sale, modulo $1.000.000.007$.

h2. Date de intrare

h2. Date de ieşire

Pe prima linie a fişierului de ieşire $papagali.out$ se va afla numărul de scheme de papagali care pot fi realizate în situaţia iniţială. Pe linia $i+1$ ({$1≤i≤Q$}) se va afla numărul maxim de scheme de papagali care se pot obtine prin achizitionarea a $X{~i~}$. noi papagali. Aceste numere vor fi afişate modulo $1 000 000 007$.

Pe prima linie a fişierului de ieşire $papagali.out$ se va afla numărul de scheme de papagali care pot fi realizate în situaţia iniţială. Pe linia $i+1$ ({$1≤i≤Q$}) se va afla numărul maxim de scheme de papagali care se pot obtine prin achizitionarea a $X{~i~}$. noi papagali. Aceste numere vor fi afişate modulo $1.000.000.007$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $0$ ≤ $N$, $K$, $Q$ ≤ $200.000$
 

h2. Exemplu