Description

众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：

对于一张无向图，独立集定义为图的一个点集S满足S中任意两点之间都不存在一条边。

定义一棵树的权值为这棵树的最大独立集大小。

现在勇太想要知道节点数a∈[1,n]，权值b∈[0,n]的有根树分别有多少棵，答案可能很大，他只想知道对9982 44353取模后的结果。

在这个问题中每一个节点的儿子视为有序且互不相同的，具体可以见样例解释。

当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？

Format

Input

输入第一行包含一个整数n。n <= 500

Output

输出n行每行n+1个整数，第i行第j列表示i个节点权值为j-1的树的个数。

Samples

4

0 1 0 0 0
0 1 0 0 0
0 0 2 0 0
0 0 3 2 0

Source By jiry_2