Fişierul intrare/ieşire:	papagali.in, papagali.out	Sursă	Junior Challenge 2020
Autor	Alexa Tudose	Adăugată de	Comisia •JuniorChallenge2020
Timp execuţie pe test	0.35 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Papagali

În ciuda aparenţelor, K0kalaru47 este un mare iubitor al animalelor, în special al papagalilor. El deţine N papagali aparţinând unui număr de K specii, câte A_i papagali din specia i. Se garantează că A_i este par. El doreşte să îşi extindă colecţia cât mai curând.

K0kalaru47 are Q planuri de a-şi extinde colecţia. Pentru fiecare plan i, el îşi doreşte să achiziţioneze X_i papagali noi, aparţinând celor K specii. El va face acest lucru astfel încât să aibă în continuare tot un număr par de papagali din fiecare specie (altfel papagalii s-ar simţi singuri). K0kalaru47 e mare fan al schemelor de papagali, deci vrea să achiziţioneze noii papagali astfel încât numărul de scheme de papagali care vor putea fi efectuate după aceea să fie cât mai mare. La aceste scheme participă atât papagalii pe care îi avea deja, cât şi cei X_i papagali noi.

În viziunea sa, o schemă cu papagali este definită astfel: papagalii se aşează într-un şir, apoi fiecare papagal îşi alege o pereche din aceeaşi specie cu el. Fiecare papagal va aparţine exact unei perechi. K0kalaru47 consideră că două scheme sunt diferite dacă şi numai dacă cel puţin una dintre următoarele condiţii este îndeplinită:

1. Există o poziţie x astfel încât papagalul de pe poziţia x din prima schemă aparţine altei specii decât papagalul de pe poziţia x din a doua schemă.
2. Există două poziţii x şi y astfel încât papagalii de pe poziţiile x si y sunt într-o pereche în prima schemă, dar nu sunt într-o pereche în a doua schemă.

Cerinţă

K0kalaru47 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 10⁹ + 7.

Date de intrare

Pe prima linie a fişierului de intrare papagali.in se vor regăsi N şi K.
Pe cea de-a doua linie se vor afla A₁, A₂, ..., A_K.
Pe cea de-a treia linie se va afla Q.
Pe cea de-a patra linie se vor afla valorile X₁, X₂, ..., X_Q.

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 10⁹ + 7.

Restricţii

• 0 ≤ N, Q ≤ 200.000
• 1 ≤ K ≤ 200.000
• 0 ≤ X_i ≤ 400.000
• N, A_i, şi X_i sunt pare
• Pentru teste în valoare de 10 puncte, K = 1
• Pentru teste în valoare de 30 de puncte, Q = 0
• Pentru teste în valoare de 20 de puncte, K, Q ≤ 2000 şi X_i ≤ 4000

Exemplu

Explicaţie

În primul exemplu sunt 45 de scheme care se pot face cu papagalii iniţiali. Câteva dintre aceste scheme sunt:

• Aşezăm papagalii din prima specie pe primele 4 poziţii şi papagalii din a doua specie pe ultimele 2 poziţii. Formăm perechi între papagalii de pe poziţiile 1 şi 2, 3 şi 4, 5 şi 6.

• Aşezăm papagalii din prima specie pe primele 4 poziţii şi papagalii din a doua specie pe ultimele 2 poziţii. Formăm perechi între papagalii de pe poziţiile 1 şi 3, 2 şi 4, 5 şi 6.

• Aşezăm papagalii din prima specie pe poziţiile 1, 3, 5 şi 6 şi papagalii din a doua specie pe poziţiile 2 şi 4. Formăm perechi între papagalii de pe poziţiile 1 şi 6, 3 şi 5, 2 şi 4.

• Aşezăm papagalii din prima specie pe poziţiile 1, 2, 4 şi 6 şi papagalii din a doua specie pe poziţiile 3 şi 5. Formăm perechi între papagalii de pe poziţiile 1 şi 6, 3 şi 5, 2 şi 4.

Dacă în planul din primul exemplu achiziţionăm alţi doi papagali din a doua specie, vom putea face 630 de scheme, acesta fiind numărul maxim posibil.

Cum se trimit solutii?