Problem 1032. -- Partition

1032: Partition

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board]

Description

一天,超人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这样累下去吧?希望你能编一个程序,算出这个总数。

Input

有多组测试数据。
每组数据仅有一个n(1≤n≤200),独占一行,表示城市A和B之间的超里数。
最后以0结尾。

Output

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

Sample Input

4
7
8
0

Sample Output

2
5
6

HINT

对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种。

Source

[Submit][Status]