题目描述

墙上有三角形木板，上面钉着n(n+1)/2颗钉子。下面有(n+1)个格子，例如n=5时如下图1：


钉子和周围的钉子的距离都是d。让一个直径略小于d的小球中心正对着上面的钉子在板上自由落体，小球每碰到一个钉子都可能落向左边或右边。图2就是小球落入第5格的一条可能的路径。

现在有些钉子被拔掉（保证第n行的钉子都不会拔掉），小球到被拔掉钉子的位置，就只能垂直下落。如图3，其中第4行的第2个钉子被拔掉了。问小球落入下面每一个格子各有多少可能路径？

输入格式

第1行为整数n（2<=n<=50）。

以下n行依次为木板上从上至下n行钉子的信息，每行中1表示钉子还在，0表示钉子被拔去。

输出格式

n+1个整数。

输入/输出例子1

5
1
1 0
1 1 1
1 0 1 1
1 1 1 1 1

1 2 5 4 2 0