题目 3：网格行走 (Grid Walk)

题目描述

你现在位于一个 $N \times M$ 网格的左上角单元格，目标是通过一系列步骤到达右下角单元格。

• 移动规则：每一步你可以向右移动一格，或者向下移动一格。
• 限制条件：你不能移动到“被阻塞”的单元格中。

请编写一个程序来计算到达右下角单元格的路线总数。注意，路径数可能为 0。题目保证左上角单元格不会被阻塞。

输入格式

• 第一行包含两个以空格分隔的整数 $N$ 和 $M$（$1 \le N, M \le 1000$）。
• 接下来的 $N$ 行，每行包含 $M$ 个字符，描述网格的每一行。
  • . 代表空单元格。
  • # 代表阻塞单元格。

输出格式

输出一个整数，代表到达右下角的方法总数。 由于这个数字可能非常大，请输出其除以 $10^8$ 后的余数（取模 $100,000,000$）。

例如：如果答案是 1038000432，则输出 38000432；如果答案是 1700060120，则输出 60120。

计分与子任务

• 子任务 1 (0 分)：样例测试。
• 子任务 2 (10 分)：$N = 1$。
• 子任务 3 (20 分)：$N = 2$。
• 子任务 4 (20 分)：$1 \le N, M \le 7$。
• 子任务 5 (20 分)：没有任何阻塞单元格（纯数学组合问题）。
• 子任务 6 (30 分)：无其他限制。