425. 走方格4
时间限制：1000 MS 内存限制：128 MB
题目描述
## 题目描述 走方格是动态规划的一个经典问题，它问的是在一个$n\timesm $的网格中，每一步只能往右或者往上走，问从左下角走到右上角的方案数，如果你说你还不知道这个问题该怎么解决，那也没有关系，因为这并不妨碍你思考下面的问题。 现在我们给出一个$n\times2n$ 的网格，定义左下角为 $(0,0)$，右上角为 $(n,2n)$，每一步只能往右走或者上走，我们问的也是从左下角到右上角的方案数。但是为了增加趣味性，我们在左下角和右上角之间画一条线，在行走的过程中，不允许走到这条线的上方，可以踩到线。 例如当$ n=2 $的时候，一共有下面这 $3 $种方案： ## 输入格式 多组输入 每组输入在一行中给出一个正整数 $n$ 当在一行中给出一个数字$ 0$ 时表示输入结束 - $1\len\le10000$ ## 输出格式 对于每组输入在一行中输出一个正整数表示答案 如果答案大于 $10000$，那就输出答案的最后四位即可 ## 输入 ```in1 2 7 0 ``` ## 输出 ```out1 3 7752 ``` ## 提示