F. Примулагийн цуглуулга

хугацааны хязгаарлалт 8 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

МММ-тэй (Mischievious Mess Makers) найрамдахын тулд Бэсси болон фермер Жон нар Бовинийн үржил шимт газрыг цэцэрлэгжүүлэхээр болжээ. Цэцэрлэг бүр яг ижил эрэмбэ дарааллаар цэцгүүдээ байршуулсан байх ёстойг мэргэжилтнүүд андахгүй. Анхлан фермер Жон $n$ төрлийн өөр өөр цэцгүүд тарьж чадах ба $i$-р төрлийн цэцгээс $a_{i}$ ширхгийг ургуулах боломжтой байв.

Дараагийн $q$ өдрийн турш фермер Жон шинэ төрлийн цэцгийн багцууд хүлээн авсаар байх ба $j$-р өдөр нэг төрлийн $c_{j}$ цэцэг ирэх ба энэ нь түүнд өмнө нь байсан цэцгүүдээс өөр төрлийнх болно.

Хэт үрэлгэн болон хэмнэлттэй байхын тэнцвэрийг олж сурсны хувьд фермер Жон яг $k$ төрлийн цэцэг л ашиглахыг хүсч буй. Цаашлаад хаягдал бага гаргахын тулд сонгосон $k$ төрөлд хамаарах цэцэг бүрийг хэрэглэх ёстой. Цэцэрлэг бүр өөр хоорондоо яг адил байх учиртай. Өөрөөр хэлбэл сонгогдсон $k$ төрлөөс нэг зүйлийн цэцэг болгон цэцэрлэг бүрт адил тоогоор байх шаардлагатай. Фермер Жон аль болон олон цэцэрлэг байгуулахыг хүсч байгаа юм.

$q$ өдрийн турш тус бүрд нь цэцгээ авсны дараагаар бүх боломжит $k$ сонголтын хувьд байгуулж болох хамгийн олон цэцэрлэгийн тоонуудын нийлбэрийг фермер Жон мэдэхийг хүсчээ. Том тоо гарч болох тул $10^{9} + 7$ тоонд хуваагаад гарах үлдэгдлийг хэвлэнэ үү.

Оролт

Эхний мөрөнд $n$, $k$ and $q$ ($1 \le k \le n \le 100 000$, $1 \le q \le 100 000$) гурван тоо өгөгдөнө.

Оролтын удаах $n$ мөрийн $i$ дэхэд нь ($1 \le i \le n$) $i$-р төрлийн цэцгээс хэд байсныг илтгэх $a_i$ ($1 \le a_i\le 1 000 000$) тоо өгөгдөнө.

Дараагийн $q$ мөрийн $j$ дэх нь ($1 \le j \le q$) $j$-р өдөр хэдэн цэцэг ирэхийг илтгэх $c_i$ ($1\le c_j \le 1 000 000$) тоог агуулна.

Гаралт

$q$ өдөр бүрийн дараа $k$ төрлийн цэцгийн бүх боломжит сонголт бүрийн хувьд хамгийн олондоо хэдэн цэцэрлэг байгуулж болох тоонуудын нийлбэрийг $10^{9} + 7$ модулиар хэвлэ.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
3 3 2
4
6
9
8
6
Гаралт
5
16
Оролт
4 1 2
6
5
4
3
2
1
Гаралт
20
21

Тэмдэглэл

Эхний жишээнд анхны өдрийн дараагаар фермер Жонд цэцэг бүрээс $(4, 6, 9, 8)$ байх ба $k = 3$.

$(4, 6, 8)$ гэж сонговол цэцэг бүрээс $(2, 3, 4)$ тоогоор аваад $2$ ширхэг цэцэрлэг байгуулах боломжтой. $(4, 6, 9)$, $(4, 9, 8)$, $(6, 9, 8)$ гэж сонговол аль ч тохиолдолд ихдээ нэг л цэцэрлэг байгуулах боломжтой, учир нь илүү олон бол цэцгүүдийг жигд хуваарилж боломжгүй. Тэгэхээр $k = 3$ үед бүх боломжит сонголтуудын нийлбэр $2 + 1 + 1 + 1 = 5$.

Хоёр дах өдрийн дараа цэцэг бүрээс $(4, 6, 9, 8, 6)$ тооных байна. Бүх боломжит сонголтуудын хувьд нийлбэр $1 + 2 + 2 + 1 + 1 + 2 + 2 + 3 + 1 + 1 = 16$ гарна.

Хоёр дах жишээнд $k = 1$. $x$ цэцгээр $x$ цэцэрлэг байгуулах боломжтой. Иймд хариу нь $6 + 5 + 4 + 3 + 2 = 20$ ба $6 + 5 + 4 + 3 + 2 + 1 = 21$ юм.

Сэтгэгдлүүдийг ачааллаж байна...