J-Just Jump_2019牛客暑期多校训练营（第八场）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Gromah and LZR have entered the final level. In this level, they need to cross the sea of death to gain the treasures.

The sea of death is of width $L_{}$ , and there are $L-1_{}$ stones inside the sea. Assume that Gromah and LZR are at position $0_{}$ initially, that the treasures are at position $L_{}$ , and that stones are at position $1,2, \cdots, L-1$ respectively. So Gromah and LZR can jump on the stones to cross the sea.

Unfortunately, the stones are not stable. To ensure safety, Gromah and LZR should go forward at least $d_{}$ positions each time. Formally, if they are at position $x_{}$ currently, they should jump onto the positions not less than $x+d_{}$ . Moreover, they can't be at positions greater than $L_{}$ in any time, which means that the destination of their last jump should be exactly position $L_{}$ , or the treasure keepers will see them and come to eat them.

More unfortunately, the Infernos under the sea will attack them $m_{}$ times in total, each attack can be described as a tuple $(t,p)_{}$ , denoting that the stone at position $p_{}$ will be attacked right after their $t_{}$ -th jump, which means their destination of $t_{}$ -th jump can't be position $p_{}$ .

But fortunately, here comes the farmer(mentioned in problem I but not necessary to care in this problem) and he tells Gromah and LZR all the attack plans, so they can work out some jumping plans according to the information given by the farmer to get to the destination without being attacked.

Please help them determine the number of jumping plans satisfying all the restrictions described above. Since the number may be very large, you should report it modulo $998244353_{}$ .

Two jumping plans are considered different if there exists at least one $t_{}$ that their positions after $t_{}$ -th jump are different in two plans.

输入描述:

The first line contains three positive integers , denoting the width of the sea, the lower bound of jumping distance, and the number of attacks.

Following  lines each contains two positive integers , denoting an attack .



 attacks are pairwise distinct, where two attacks  are considered different if  or  or both.

输出描述:

Print a non-negative integer in one line, denoting the answer modulo .

示例1

输入

复制

5 2 1
1 2

输出

复制

说明

There are three plans originally : . But after the first jump, the stone at position 2 will be attacked, so plan  should be abandoned and 2 valid plans remain.