시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

Svako jutro kad se razdani, Ivan treba pogasiti sve žarulje ulične rasvjete u svom selu. Njegovo selo je slavonskog tipa, dakle jedna cesta ravna k’o ravnalo određene duljine, a rasvjetni stupovi samo s jedne strane ceste, označeni brojevima od 1 do N s lijeva na desno.

Ivan svakog dana odabere jedan početni stup p, gasi žarulju na njemu te dalje gasi žarulje pohlepnim algoritmom pokušavajući uštedjeti električnu energiju. U svakom koraku pogleda sljedeću upaljenu žarulju lijevo (ako postoji) i sljedeću upaljenu žarulju desno (ako postoji) pa krene ugasiti onu od dvije žarulje koja je veće snage. Ako ne postoji upaljena žarulja lijevo (odnosno desno), kreće ugasiti sljedeću žarulju desno (odnosno lijevo). Ako su žarulje jednake snage, Ivan može odabrati i ugasiti bilo koju od njih. Zbog toga za zadanu početnu poziciju p, može postojati više različitih rasporeda gašenja žarulja.

Označimo sa M(p) broj različitih rasporeda gašenja žarulja ako Ivan krene od pozicije p. Napišite program koji će za svaku od K zadanih početnih pozicija pi odrediti ostatak od M(pi) pri dijeljenju s 109 + 7.

입력

U prvom redu nalazi se prirodni brojevi N i K – broj stupova te broj zadanih početnih pozicija.

U drugom redu nalazi se N prirodnih brojeva A1, A2, . . . AN odvojenih jednim razmakom – snage žarulja na stupovima.

U trećem redu nalazi se K prirodnih brojeva P1, . . . , PK odvojenih jednim razmakom – početne pozicije koje nas zanimaju.

U svakom podzadatku vrijedi 1 ≤ pi ≤ N i 1 ≤ Ai ≤ 200 000. 1 ≤ N, K ≤ 200 000

출력

U prvi i jedini red izlaza potrebno je ispisati K cijelih brojeva odvojenih jednim razmakom – i-ti po redu broj treba biti jednak ostatku od M(pi) pri dijeljenju s 109 + 7.

예제 입력

5 2
3 5 1 4 3
3 5

예제 출력

2
1

예제 입력 2

7 7
7 7 7 7 7 7 7
7 6 5 4 3 2 1

예제 출력 2

1
6
15
20
15
6
1

힌트

Ako Ivan počinje od trećeg stupa, on odmah gasi žarulju na njemu – (3, 5, X, 4, 3).
Lijeva žarulja veće je snage pa gasi nju – (3, X, X, 4, 3).
Sada je desna žarulja veće snage pa gasi nju – (3, X, X, X, 3).
Ivan ima dvije mogućnosti za posljednji korak jer su žarulja broj 1 i žarulja broj 5 iste snage.

Ako Ivan počinje od petog stupa, jedini način na koji može pogasiti žarulje je da se kreće s desna na lijevo i redom ih gasi.