Description

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

Input

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

Output

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

Sample

Input

1
2
3
0

Output

1
3
8

Source: DK