蚂蚁寻路问题

题目描述

小蚂蚁是蚂蚁王国的一名快递员，每天需要从王国的仓库运送食物。在一个由 $n$ 行 $m$ 列组成的网格中，一只小蚂蚁要从网格的左下角出发，爬到网格的右上角。小蚂蚁每次只能向上或向右移动一格，不能向下或向左移动。小蚂蚁想知道，从起点 $(0,0)$ 到终点 $(n,m)$ 一共有多少条不同的路径。由于答案可能非常巨大，我们只需要知道答案的最后 $100$ 位数字。

输入格式

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

输出格式

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

样例 #1

输入 #1

2 2

输出 #1

0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000006

数据范围

对于 $30\%$ 的数据，$0<n,m\le 10$；

对于 $50\%$ 的数据，$0<n,m\le 100$；

对于 $100\%$ 的数据，$0<n,m\le 50000$。