UOJ Logo Universal Online Judge

UOJ

#209. 【UER #6】票数统计

统计

妹滋滋是一个善于编程的女孩子。

但是某一天,她一不小心把 UOJ 后台的票数统计程序写错了。

本来嘛在这种根本没有什么用的功能上出了 bug 也没有什么大关系,但是又有某一天,UOJ 突然就开始搞全民公投了。

这可怎么办呢?如果这个消息让别人知道的话自己肯定会被查表,更不要说让所有用户重新来投一次票了。

作为一个要强的女孩子,妹滋滋决定自力更生。

通过一些奥妙重重的方式,妹滋滋知道了一些关于这次全民公投的信息。

  1. 这次全民公投一共有 $n$ 位用户排队参加,编号为 $1$ 到 $n$。每一位用户要么投了通过,要么投了不通过。
  2. 有 $m$ 个二元组 $(x_i,y_i)$,每个二元组给出这样一个信息: “前 $x_i$ 位用户中,恰好 $y_i$ 位投了通过” 和 “后 $y_i$ 位用户中,恰好有 $x_i$ 位投了通过” 这两句话中,至少有一句是成立的。

作为分析的第一步,她想要知道有多少种投票情况是满足她所得到的信息的。当然,可能所有投票情况都不满足条件。

输入格式

输入第一行一个正整数 $T$ 表示数据组数。

对于每组数据,第一行有两个空格隔开的正整数 $n,m$。

接下来 $m$ 行每行两个空格隔开的正整数 $x_i,y_i$,保证 $0 \leq x_i,y_i \leq n$ 且 $x_i,y_i$ 不全为 $0$。

输出格式

对于每组数据输出一行表示答案,答案可能很大,只需要输出对 $998244353$($7 \times 17 \times 2^{23} + 1$,一个质数) 取模后的值。

样例一

input

2
3 1
2 1
5 3
1 3
4 2
3 1

output

4
2

explanation

用 $0$ 表示不通过,$1$ 表示通过。

满足第一组数据的情况有:$(100),(101),(010),(011)$。

满足第二组数据的情况有:$(10010),(01010)$。

样例二

见样例数据下载。

限制与约定

测试点编号 $n$ $m$ 约定
1$n \leq 20$$m \leq 20$
2
3
4$m \leq 1000$
5
6$n \leq 5000$保证 $x_i \lt y_i$
7$n \leq 60$$m \leq 60$
8
9$n \leq 5000$$m \leq 1000$
10

对于所有数据,$T \leq 5$。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载