#230. 机器人走方格

    ID: 230 Type: Default 1000ms 256MiB Tried: 1 Accepted: 1 Difficulty: 10 Uploaded By: Tags>动态规划2024寒假一期结训赛

机器人走方格

Background

zjz非常喜欢机器人,因此他举办了一个机器人参加走方格大赛。

Description

在一个 N×MN \times M 的场地中,你的机器人起点位于左上角(0,0)(0, 0),终点为右下角(N,M)(N, M)。场地中有一些位置有障碍物,不能走有障碍物的位置。

由于要快速到达终点,他给他的机器人设定了一个限制,只能往下走或往右走;同时,他也给他的机器人增加了一个好玩的设定,就是每一步都由机器人自己随机选择往下或往右。

请你计算出这种情况下他的机器人一共有多少种走到终点的走法。

由于答案可能很大,因此你的答案需对998244353998244353取模。

Format

Input

一行输入两个整数 NNMM,表示场地的大小。

接下来一行输入一个整数 KK ,表示场地有 KK 个障碍物。

接下来 KK 行每行输入两个整数 ii jj,表示在 (i,j)(i, j) 位置有一个障碍物。

Output

输出一个整数,表示机器人的走法对998244353998244353取模的结果。

Samples

2 2
1
2 0
5