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

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ă credţi 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.$