4. 蚂蚁寻路问题

题目描述

小蚂蚁是蚂蚁王国的一名快递员，每天需要从王国的仓库运送食物。在一个由 (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

数据范围

• 对于 (30%) 的数据，(0 < n, m \leq 10)
• 对于 (50%) 的数据，(0 < n, m \leq 100)
• 对于 (100%) 的数据，(0 < n, m \leq 50000)