Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Паметни кодер Аки је синоћ гледао филм ”Ocean’s eleven” (Играј своју игру). Како му је филм био досадан, негде на половини се успавао и почео да сања о томе како може преварити кладионицу као актери филма. Сањао је да има приступ бази података кладионице и да може наместити резултат било које утакмице.
Одлучио је да се клади на фудбалске мечеве. Постоји \(N\) различитих фудбалских лига, а у свакој лиги по \(M\) утакмица за које је могуће уложити опкладу. За сваку утакмицу коју је одабрао је позната квота - природан број који представља коефицијент добитка који носи та утакмица уколико је резултат погођен.
Аки ће из сваке лиге изабрати бар једну утакмицу (могуће и више), и тако саставити тикет. За сваку лигу је познат број утакмица које је могуће изабрати из те лиге на истом тикету - нпр. постоји случај где је за неку лигу могуће изабрати тачно 2 или 4 утакмице, али није могуће изабрати 3.
Добитак тикета се одређује тако што се помноже квоте свих одабраних утакмица, а затим се добијени производ помножи са бонусом који зависи од броја одиграних утакмица. Бонуси за сваки могући број одиграних утакмица су дати од стране кладионице.
Како Аки у свом сну може наместити резултате свих утакмица, и жели да заради што више пара, он ће саставити све могуће тикете. Два тикета се разликују уколико бар једна утакмица постоји на једном тикету, а не постоји на другом. На крају, Аки ће зарадити онолико пара колико је збир добитака са свих тикета.
Израчунајте и испишите колико ће пара Аки зарадити у свом сну (рачунајући по модулу \(10^9 + 7 = 1000000007\)).
У првом реду се налазе два природна броја: \(N\) - број лига, и \(M\) - број утакмица у свакој лиги. У наредних \(N\) редова се налази по \(M\) природних бројева који представљају квоте за сваку утакмицу.
У следећих \(N\) редова се налази по \(M\) бројева који представљају матрицу \(C\). Елементи те матрице могу имати вредност нула или један. Ако је \(j\)-ти број у \(i\)-том од тих редова једнак један (\(C[i][j]=1\)), онда то значи да се из \(i\)-те лиге може изабрати \(j\) утакмица, а ако је једнак нули, онда се из \(i\)-те лиге не може изабрати \(j\) утакмица.
У последњем реду улаза има укупно \(N \times M\) природних бројева где \(i\)-ти број у низу предстаља бонус за укупно одиграних \(i\) утакмица.
У првом реду излаза исписати колико ће пара Аки зарадити, рачунајући по модулу \(10^9 + 7 = 1000000007\).
<div class="panel panel-default">
<div class="panel-heading">
<span class="pull-left" style="width: 48%;">Ulaz</span>
<span style="padding-left: 15px;">Izlaz</span>
</div>
<div class="panel-body">
<span class="pull-left exampleinput">
2 3<br/>
2 3 4<br/>
5 6 7<br/>
1 0 1<br/>
0 1 1<br/>
10 20 30 40 50 60
</span>
<span class="exampleoutput">
535290
</span>
</div>
</div>Постоје две лиге са по три утакмице. Квоте утакмица у првој лиги су \(2\), \(3\) и \(4\), док у другој лиги постоје утакмице са квотама \(5\), \(6\) и \(7\). Из прве лиге је могуће изабрати тачно једну или тачно три утакмице, док није могуће изабрати две утакмице из прве лиге. Из друге лиге је могуће изабрати две или три утакмице. Неки од могућих тикета су: * Из прве лиге бирамо прву утакмицу (квота \(2\)), из друге лиге бирамо прву и другу утакмицу (квоте \(5\) и \(6\)). Укупна квота је \(2 \cdot 5 \cdot 6 = 60\). Пошто смо изабрали 3 утакмице, квота се множи са бонусом за 3 утакмице (\(30\)), и тако добијамо укупан добитак за овај тикет: \(60 \cdot 30 = 2400\) * Из прве лиге бирамо све три утакмице (квоте \(2\), \(3\) и \(4\)), из друге лиге бирамо прву и трећу утакмицу (квоте \(5\) и \(7\)). Укупна квота је \(2 \cdot 3 \cdot 4 \cdot 5 \cdot 7 = 840\). Како смо изабрали укупно 5 утакмица, квота се множи са бонусом ѕа 5 утакмица (\(50\)) и тако добијамо укупан добитак: \(840 \cdot 50 = 42000\)
Комбиновањем свих могућих тикета, а онда сабирањем њихових добитака, добијамо укупну зараду од \(535290\).
Постоје \(5\) подзадатака, у којима додатно важи: