TopCoder

Thumb
柊 四千
あぅあぅ~

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

67.6% (50/74)

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

2 3
1 2 1
1 1 2

Sample Output

2 4 6

Hints

Problem Source

原TIOJ1708 / 建國中學99年校內培訓contest #7 prob 4
problem setter:suhorng

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 3000 65536
1 3000 65536
2 3000 65536
3 3000 65536
4 3000 65536
5 3000 65536
6 3000 65536
7 3000 65536
8 3000 65536
9 3000 65536