#描述#
生成树是计算机专业考研大纲中数据结构的一部分。DK在复习这一部分时，会去数一个图的生成树个数。一个有n+1个顶点{ 0, 1, ..., n } 和2n-1条边的图叫做“n-fan图”，定义如下： 顶点0与其他n个顶点均用一条边相连，顶点k与顶点k+1用一边相连（1 <= k < n）试求这个图的生成树个数。

#格式#
##输入格式##
有多组数据，对于每组数据，有一个整数n(1&lt=n&lt=1e9)，表示“n-fan图”的n，n=0表示输入结束。

##输出格式##
输出“n-fan图”中所有不同的生成树的数目，并把结果模20090329。

#样例1#
##样例输入1##

1
2
3
0

##样例输出1##

1
3
8

#限制#
1000ms
32768KB

#提示#

#来源#
DK