蚂蚁寻路问题

题目背景

小蚂蚁是蚂蚁王国的一名快递员，每天需要从王国的仓库运送食物。在一个由 n 行 m 列组成的网格中，一只小蚂蚁要从网格的左下角出发，爬到网格的右上角。小蚂蚁每次只能向上或向右移动一格，不能向下或向左移动。

小蚂蚁想知道，从起点 (0,0) 到终点 (n,m) 一共有多少条不同的路径。由于答案可能非常巨大，我们只需要知道答案的最后 100 位数字。

输入格式

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

输出格式

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

样例一

输入数据

2 2

输出数据

0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000006

样例解释

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

右→右→上→上

右→上→右→上

右→上→上→右

上→右→右→上

上→右→上→右

上→上→右→右

数据规模与约定

对于 30% 的数据，0<n,m≤10

对于 50% 的数据，0<n,m≤100

对于 100% 的数据，0<n,m≤50000