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 ≤ 14$.
* Pentru alte $40$ de puncte, $N, K ≤ 500$.

* subtaskuri chestii

h2. Exemplu