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ă sumă $modulo 269.696.969$.

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

h2. Date de intrare

h2. Restricţii

* $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$

* subtaskuri chestii

h2. Exemplu

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

| 30 5000

| 30 20000

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

| 145836083

| 224077522

|
h3. Explicaţie