尤拉是一位数学家,他对世界的认知是如此绝对,就好像他已经解决了一百万亿亿年的形式问题一样。这个问题仅此而已!
考虑区间 $$$[0, 10^{n})$$$ 中的所有非负整数。为了方便起见,我们用前导零对所有数字进行补足,使得给定区间中的每个数字恰好由 $$$n$$$ 十进制数字组成。
给你一组$$$(u_i, v_i)$$$,其中$$$u_i$$$ 和$$$v_i$$$ 是从$$$0$$$ 到$$$9$$$ 的不同十进制数字。
考虑一个由 $$$n$$$ 数字组成的数字 $$$x$$$。我们将从左到右枚举所有数字,并将它们表示为 $$$d_1, d_2, \ldots, d_n$$$。在一次操作中,当且仅当集合中存在一对 $$$(u_j, v_j)$$$ 且至少满足以下条件之一时,您可以交换数字 $$$d_i$$$ 和 $$$d_{i + 1}$$$:
1. $$$d_i = u_j$$$ 且 $$$d_{i + 1} = v_j$$$,
2. $$$d_i = v_j$$$ 且 $$$d_{i + 1} = u_j$$$。
我们将由 $$$n$$$ 数字组成的数字称为 $$$x$$$ 和 $$$y$$$,如果可以使用上述一些操作将数字 $$$x$$$ 转换为数字 $$$y$$$,则等效。特别是,每个数字都被认为与其自身相等。
给你一个整数 $$$n$$$ 和一组 $$$m$$$ 数字对 $$$(u_i, v_i)$$$。您必须找到最大整数 $$$k$$$,使得存在一组整数 $$$x_1, x_2, \ldots, x_k$$$ ($$$0 \le x_i < 10^{n}$$$),使得对于每个 $$$1 \le i < j \le k$$$,数字 $$$x_i$$$ 不等于数字 $$$x_j$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50\,000$$$) — 所考虑数字的位数。
第二行包含一个整数 $$$m$$$ ($$$0 \le m \le 45$$$) — 集合中数字对的数量。
以下 $$$m$$$ 行均包含两个数字 $$$u_i$$$ 和 $$$v_i$$$,以空格分隔 ($$$0 \le u_i < v_i \le 9$$$)。
保证所有描述的对都是成对不同的。
输出
打印一个整数 - 最大值 $$$k$$$,使得存在一组整数 $$$x_1, x_2, \ldots, x_k$$$ ($$$0 \le x_i < 10^{n}$$$),使得对于每个 $$$1 \le i < j \le k$$$,数字 $$$x_i$$$ 不等于数字$$$x_j$$$。
由于答案可能足够大,因此打印数字 $$$k$$$ 模 $$$998\,244\,353$$$。
示例
输入 #1
1 0
输出 #1
10
输入 #2
2 1 0 1
输出 #2
99
输入 #3
2 9 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9
输出 #3
91
注意
在第一个示例中,我们可以构造一个包含从 $$$0$$$ 到 $$$9$$$ 的所有整数的集合。很容易看出集合中没有两个相等的数字。
在第二个示例中,存在一对唯一的等效数字:$$$01$$$ 和 $$$10$$$。我们可以构造一个包含从 $$$0$$$ 到 $$$99$$$ 的所有整数的集合,尽管数字为 $$$1$$$。