Pe scurt, vrem să aflăm suma din <tex>f(x[1], x[2], ..., x[N]) = \displaystyle\prod_{i=1; x[i] \neq 0}^{N} x[i] * hazard[i]</tex> pentru toate configuraţiile posibile ale lui $x$, astfel încât <tex>x[1] + x[2] + ... + x[N] = K</tex>.

Deoarece jocul poate deveni foarte periculos, iar tinerii de la informatică sunt periculoşi, se cere această suma $modulo 269.696.969$.

Deoarece jocul poate deveni foarte periculos, iar tinerii de la informatică sunt periculoşi, se cere această sumă $modulo 269.696.969$.

h2. Date de intrare

h2. Restricţii

* subtaskuri chestii

* $1 ≤ N, K ≤ 5.000$
* $1 ≤ hazard[{@i@}] ≤ 100.000.000$
* Pentru $10$ puncte, $N, K ≤ 12$
* Pentru alte $40$ de puncte, $N, K ≤ 300$
* Pentru alte $30$ de puncte, $N, K ≤ 2.000$

h2. Exemplu

1 2 3 4 5 6 7 8 9 10
| 261463837
|

| 30 20000

| 30 5000

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

| 224077522

| 145836083

|
h3. Explicaţie

Dacă turnăm suc doar din tipul 1, atunci vom avea $x = {3, 0}$, deci $f({3, 0}) = x[1] * hazard[1] = 3 * 2 = 6$.
Dacă turnăm suc doar din tipul 2, atunci vom avea $x = {0, 3}$, deci $f({0, 3}) = x[2] * hazard[2] = 3 * 3 = 9$.

Dacă turnăm suc doar din tipul 1, atunci vom avea $x = {3, 0}$, deci $f({3, 0}) = x[{@1@}] * hazard[{@1@}] = 3 * 2 = 6$.
Dacă turnăm suc doar din tipul 2, atunci vom avea $x = {0, 3}$, deci $f({0, 3}) = x[{@2@}] * hazard[{@2@}] = 3 * 3 = 9$.

Dacă turnăm suc din ambele tipuri, atunci $x$ va avea mai multe soluţii:

* $x = {1, 2}$, deci $f({1, 2}) = (x[1] * hazard[1]) * (x[2] * hazard[2]) = (1 * 2) * (2 * 3) = 12$.
* $x = {2, 1}$, deci $f({2, 1}) = (x[1] * hazard[1]) * (x[2] * hazard[2]) = (2 * 2) * (1 * 3) = 12$.

 
* $x = {1, 2}$, deci $f({1, 2}) = (x[{@1@}] * hazard[{@1@}]) * (x[{@2@}] * hazard[{@2@}]) = (1 * 2) * (2 * 3) = 12$.
* $x = {2, 1}$, deci $f({2, 1}) = (x[{@1@}] * hazard[{@1@}]) * (x[{@2@}] * hazard[{@2@}]) = (2 * 2) * (1 * 3) = 12$.

Deci răspunsul va fi $f({0, 3}) + f({3, 0}) + f({1, 2}) + f({2, 1}) = 6 + 9 + 12 + 12 = 39$.

Pentru al doilea şi al treilea exemplu, comisia nu mai ţine minte cât de nebun a fost jocul, în schimb a aflat a doua zi, aşa că va trebui să credem pe cuvânt sursele externe.

Pentru al doilea şi al treilea exemplu, comisia nu mai ţine minte cât de nebun a fost jocul, în schimb a aflat a doua zi, aşa că va trebui să credeţi pe cuvânt sursele externe.

$Observaţie: al treilea exemplu este pus pe 3 rânduri din motive de formatare.$