1708 . 裝配線
TopCoder
Tags
Description
經過幾千年的研發後，你終於成功了開發新的產品：Programmable Outstanding Interpreter
x8086，簡稱 POIx86。這種全新的機器人甚至還有 
Rujia Liu 說 讚！這真是太強大了！
然而，最麻煩的，就是的機器人的製造。POIx86機器人總共有 n個型別，編號 POIx86-k
型機器人製造的過程中，需要經過 k 個工作階段，而在你的工廠中總共有 m個工作廠房，每
個工作廠房，都可以完成 POIx86機器人任一個階段的工作。舉例來說，下圖就是經過9個工
作階段、2個工作廠房的POIx86-9型機器人。
製造機器人的過程中，若經過 w1 , w2 , … , wk 等k 個廠房，則必須滿足 w1 < w2 < …< wk。
也就是說，不能先經過編號大的廠房，再經過編號比較小的廠房；但究竟要在一個廠房中完成
多少個工作階段則沒有限制。因為你現在要製造的是 POIx86-n型機器人，所以只要總經過的
工作階段數是 n就好。當然也可以在單一一個廠房中把所有的工作階段都完成。
神秘的是，若你現在總共經過 w1 , w2 , … , wk 等k 個廠房，而在第i 個廠房中走過了 si個
工作階段，那總共會有 awi,si種方式來完成這件工作！換句話說，前述的這些條件下，
你完成這個機器人的方法數總共有 aw1,s1 × aw2,s2 × … × awk,sk種！
傑克，這真是太神奇了！身為一個TIOJer 的你，當然想知道：分別有幾種完成 POIx86-1到POIx86-n型機器人的方式呢？
Input Format
佔總分20% 的測資中，1 ≤ n ≤ 1,000。
佔總分50% 的測資中，1 ≤ n ≤ 10,000。
對於所有的測資，1 ≤ n ≤ 30,000、1 ≤ m ≤ 5
輸入的第一行有兩個正整數，分別是 m、n。接下來有 m行，每行有 n個非負整數，第 i＋1行
的第j 個整數分別代表在編號 i 的廠房完成 j 個階段的工作有幾種方法(即ai,j)。
Output Format
請輸出n個數字，第 i 個數字代表完成 POIx86-i 型的機器人有幾種方法。
因為答案有可能很大，所以你只要輸出方法數除以264的餘數就好。
Sample Input 1
1 2 1
1 1 2
Sample Output 1
Hints
Problem Source
原TIOJ1708 / 建國中學99年校內培訓contest #7 prob 4
problem setter:suhorng
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |