#9279. 「第9次PTA认证」蚂蚁寻路问题 普及+/提高

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Wind_Rises

题目描述

小蚂蚁是蚂蚁王国的一名快递员,每天需要从王国的仓库运送食物。在一个由 列组成的网格中,一只小蚂蚁要从网格的左下角出发,爬到网格的右上角。

小蚂蚁每次只能向上或向右移动一格,不能向下或向左移动。小蚂蚁想知道,从起点 (0,0) 到终点 (n,m) 一共有多少条不同的路径。由于答案可能非常巨大,我们

只需要知道答案的最后 位数字。

输入格式

输入只有一行,包含两个整数 ,分别表示网格的行数和列数。

输出格式

输出共 行,每行十个数字,没空格间隔,表示答案的最后 位。如果答案不足 位,则在前面用 补足。

样例

样例输入

2 2

样例输出

0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000006

样例解释

2×2 的网格中,从左下角到右上角的路径数为 ,具体路径如下:

右→右→上→上

右→上→右→上

右→上→上→右

上→右→右→上

上→右→上→右

上→上→右→右

数据范围与提示

对于 的数据,

对于 的数据,

对于 的数据,