1031. 传球问题

单点时限: 2.0 sec

内存限制: 256 MB

排球课上,老师进行在共青场进行传球练习,一共有 p 人参加,一开始球在你的手里。每次传球时,持球者都会把球传给另外一个人。传了 n 次后,球又回到了你的手里。现在老师想知道有多少种传法,他说如果给出答案,会有奖励的。于是大家各自开动大脑,想办法解决。作为计算机系的你,想要写一个程序来解这个问题……

提示:

例如,对于 p=4,n=4,有 21 种传法。设四人分别为甲、乙、丙、丁,你是甲。若第一次球传给乙,则有以下 7 种传法:甲乙甲乙甲,甲乙甲丙甲,甲乙甲丁甲,甲乙丙乙甲,甲乙丙丁甲,甲乙丁乙甲,甲乙丁丙甲。若第一次传给丙和丁,同理各有 7 种传法。共计 21 种。

输入格式

本题有多组测试数据。

每组数据一行,每行有两个整数 p 和 n。其中,2<=p<=1000000,2<=n<=2^31-1。

当一行中的 p 和 n 都为 0 时,输入结束。

输出格式

每组数据输出一行,每行一个整数。因为数字可能会非常大,所以你只要输出总数除 2005 的余数即可。

样例

Input
4 4
4 10
1000 1000
0 0
Output
21
728
1

45 人解决,105 人已尝试。

55 份提交通过,共有 360 份提交。

5.8 EMB 奖励。

创建: 16 年,11 月前.

修改: 4 年,8 月前.

最后提交: 1 月,3 周前.

来源: 2005计算机系程序设计竞赛

题目标签