TopCoder

柊 四千
あぅあぅ~

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

69.7% (53/76)

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

2 3
1 2 1
1 1 2

Sample Output 1

2 4 6

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10