问题描述

一天，超人 gush 和超人 prince 在一起玩游戏。他们想一起从城市 A 飞到城市 B。但是如果一下子就飞到城市 B 了，那实在是太没意思了。于是他们约定，飞 $k$ 次飞到 B（$k=0$ 表示一口气飞到 B）。一次可以飞任意远的距离。

但是对超人来说，飞行是家常便饭、小事一桩。因此 gush 和 prince 觉得这样玩不过瘾。这时候 gush 提议，说：下星期要考超数（“超数”是超人世界的一种考试科目，相当于我们这里的高数），不能总是玩了，干脆这次游戏也顺便锻炼一下自己的数数能力，好为下星期的考试做准备。prince 听了，觉得这个提议不错，于是提出了具体的游戏方案：

两人一起从城市 A 飞到城市 B，可以飞一段距离后休息一下，欣赏一下周围的风景，再继续飞。比如 A 和 B 距 $10$ 超里（“超里”是超人世界的一种距离单位），那么两人可以先飞 $3$ 超里，休息一下，再飞 $1$ 超里，休息一下，最后一口气飞 $6$ 超里，到达城市 B。gush 和 prince 打算统计一下，到底有多少种不同的飞行方式可以从 A 飞到 B。

所谓飞行方式，比如 $10$ 超里的路程，先飞 $3$ 超里，再飞 $4$ 超里，最后飞 $3$ 超里，这种“$3$ $4$ $3$”的形式就是对 $10$ 超里的路程而言的一种飞行方式。注意，“$3$ $4$ $3$”和“$3$ $3$ $4$”、“$4$ $3$ $3$”都算同一种飞行方式，因为都是“飞两个 $3$ 超里休息一下，飞一个 $4$ 超里休息一下”的模式。

但是 gush 和 prince 还嫌这种飞行方式过于简单，于是约定，飞行的超里数必须是奇数，在这个前提下再来统计不同的飞行方式。例如对 $10$ 超里的路程而言，“$3$ $7$”的飞行方式会被两个超人统计，但是上面提到的“$3$ $4$ $3$”，由于有一段飞行路程是 $4$ 超里，是个偶数，因此这个飞行方式将不被统计。

现在，gush 和 prince 打算亲身试验，即不断往返于城市 A 和城市 B 之间，每次采取一种不同的飞行方式，以此试遍所有的飞行可能，并统计下来。

在飞行当中，gush 和 prince 发现，不同的飞行方式总数实在是太多了，数起来太麻烦。于是二人决定合体！二人合体成超级赛亚人 grince 后，又决定把飞行方式总数对 $9901$ 取模（$9901$ 是他们两人都喜欢的一个幸运数）。作出这些决定后，超级赛亚人 grince 继续往返于 A 和 B 间玩这个游戏。

你不忍心看着 grince 这样累下去吧？希望你能编一个程序，算出这个总数。

输入格式

有多组测试数据。
每组数据仅有一个 $n$（$1 \leq n \leq 200$），独占一行，表示城市 A 和 B 之间的超里数。
最后以 $0$ 结尾。

输出格式

对每组数据，仅一个数，独占一行，表示不同的飞行方式总数对 $9901$ 取模后的结果。

样例输入

4
7
8
0

样例输出

2
5
6

提示

对 $4$ 超里的距离而言，不同的飞行方式一共有“$1$ $1$ $1$ $1$”、“$1$ $3$”这两种；
对 $7$ 超里的距离而言，不同的飞行方式一共有“$1$ $1$ $1$ $1$ $1$ $1$ $1$”、“$1$ $1$ $1$ $1$ $3$”、“$1$ $3$ $3$”、“$1$ $1$ $5$”、“$7$”这 $5$ 种；
对 $8$ 超里的距离而言，不同的飞行方式一共有“$1$ $1$ $1$ $1$ $1$ $1$ $1$ $1$”、“$1$ $1$ $1$ $1$ $1$ $3$”、“$1$ $1$ $3$ $3$”、“$1$ $1$ $1$ $5$”、“$3$ $5$”、“$1$ $7$”这 $6$ 种。