F. Формализм ради формализма
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Юра, будучи математиком, уже настолько преисполнился в своем познании, что он уже сто триллионов миллиардов лет решает формальные задачи, в которых нет ни капли легенды. Эта задача именно такая!

Рассмотрим все целые неотрицательные числа из промежутка $$$[0, 10^{n})$$$. Для удобства дополним все числа ведущими нулями таким образом, чтобы любое число из данного промежутка состояло ровно из $$$n$$$ десятичных цифр.

Пусть имеется также некоторый набор пар $$$(u_i, v_i)$$$, где $$$u_i$$$ и $$$v_i$$$ — различные цифры от $$$0$$$ до $$$9$$$.

Рассмотрим число $$$x$$$, состоящее из $$$n$$$ цифр. Пронумеруем цифры слева направо и обозначим их как $$$d_1, d_2, \ldots, d_n$$$. За одну операцию разрешается поменять местами цифры $$$d_i$$$ и $$$d_{i + 1}$$$ тогда и только тогда, когда существует такая пара $$$(u_j, v_j)$$$, что верно хотя бы одно из условий:

  1. $$$d_i = u_j$$$ и $$$d_{i + 1} = v_j$$$,
  2. $$$d_i = v_j$$$ и $$$d_{i + 1} = u_j$$$.

Назовем числа $$$x$$$ и $$$y$$$, состоящие из $$$n$$$ цифр, эквивалентными, если из числа $$$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
0
Выходные данные
10
Входные данные
2
1
0 1
Выходные данные
99
Входные данные
2
9
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
Выходные данные
91
Примечание

В первом примере можно составить множество, состоящее из всех чисел от $$$0$$$ до $$$9$$$, так как никакие два числа не являются эквивалентными друг другу.

Во втором примере существует единственная пара эквивалентных чисел: $$$01$$$ и $$$10$$$. В качестве ответа можно, например, взять множество всех чисел от $$$0$$$ до $$$99$$$, кроме числа $$$1$$$.