De obicei, dacă ai două lucruri bune pe care le combini, poate să iasă un lucru şi mai bun! În problema de faţă vom vedea anumite lucruri care nu respectă această regulă.

Să explorăm un joc pe care îl joacă elevii din ziua de azi: toţi copiii au o masă cu $N$ -substanţe interzise- sucuri numerotate de la $1$ la $N$, iar în mijloc au un pahar. Pentru fiecare suc $i (1 &le; i &le; N)$ cunoaştem coeficientul $hazard[i]$. Participanţii acestui joc încep să toarne mai multe shoturi din sucuri diferite în paharul din centru. Astfel în pahar se găseşte un amestec extrem de potent care poate afecta organismul în moduri neaşteptate creat prin turnarea a exact $k$ shoturi din mai multe sucuri. Potenţa acestui amestec se calculează astfel: fie $t$ numărul de sucuri diferite turnate în pahar şi $i{~1~}, i{~2~}, ..., i{~t~}$ indicii celor $t$ sucuri diferite turnate în pahar şi $shots[i]$ numărul de shoturi turnate în pahar din sucul cu indicele $i$. Atunci potenţa acestui amestec va fi <tex>\displaystyle\prod_{j=1}^{t} shots[i_j] * hazard[i_j]</tex>

Printre tinerii din ziua de azi circulă un nou joc: ei au pe masă $N$ -substanţe interzise- sucuri numerotate de la $1$ la $N$, iar în mijloc au un pahar cu o capacitate de $K$ shoturi, iniţial gol. Fiecare suc este dăunător pentru organism, de aceea pentru fiecare suc $i (1 ≤ i)$ cunoaştem coeficientul $hazard[i]$. Jocul decurge astfel: amestecul din pahar are iniţial potenţa 1; pentru fiecare suc $i (1 ≤ N)$ putem să alegem un număr de shoturi $x[i]$ natural; dacă $x[i]$ este 0, atunci potenţa amestecului nu se modifică; în caz contrar, acesta se înmulţeşte cu $x[i] * hazard[i]$. Când paharul se umple, unul din tineri care e la rând bea amestecul acela. Pentru a demonstra că acest joc este periculos, vrem să aflăm suma potenţelor tuturor amestecurilor posibile.

Se cere sa afisati suma potentelor tuturor felurilor in care se pot amesteca sucurile, $modulo 269696969$.

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

h2. Date de intrare

Fişierul de intrare $shoturi.in$ ...

Fişierul de intrare $shoturi.in$ va conţine pe prima linie numerele $N$ şi $K$ cu semnificaţia din enunţ.
Pe a doua linie se vor afla $N$ numere separate prin câte un spaţiu reprezentând coeficientul $hazard[i]$ al fiecărui suc.

h2. Date de ieşire

În fişierul de ieşire $shoturi.out$ se va afla raspunsul $modulo 269696969$.

Fişierul de ieşire $shoturi.out$ va conţine pe prima linie suma cerută $modulo 269.696.969$.

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$

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 primul exemplu

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 din ambele tipuri, atunci $x$ va avea mai multe soluţii:

Putem alege sa turnam suc doar in primul pahar. $shots[1 ] = 3, hazard[1 ] = 2$, deci potenta este $3 * 2 = 6$.
Putem alege sa turnam suc doar in al doilea pahar. $shots[2 ] = 3, hazard[2 ] = 3$, deci potenta este $3 * 3 = 9$.
Putem alege sa turnam suc in ambele pahare. Aici sunt doua variante:

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

* $shots[1 ] = 1, shots[2 ] = 2$. Deci potenta este $(1 * 2) * (2 * 3) = 12$
* $shots[1 ] = 2, shots[2 ] = 1$. Deci potenta este $(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$.

Raspunsul este $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ă credeţi pe cuvânt sursele externe.
$Observaţie: al treilea exemplu este pus pe 3 rânduri din motive de formatare.$

== include(page="template/taskfooter" task_id="shoturi") ==