Юра, будучи математиком, уже настолько преисполнился в своем познании, что он уже сто триллионов миллиардов лет решает формальные задачи, в которых нет ни капли легенды. Эта задача именно такая!
Рассмотрим все целые неотрицательные числа из промежутка \([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)\), что верно хотя бы одно из условий:
- \(d_i = u_j\) и \(d_{i + 1} = v_j\),
- \(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\).
Выходные данные
Выведите одно число — максимальное число \(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\).
Примечание
В первом примере можно составить множество, состоящее из всех чисел от \(0\) до \(9\), так как никакие два числа не являются эквивалентными друг другу.
Во втором примере существует единственная пара эквивалентных чисел: \(01\) и \(10\). В качестве ответа можно, например, взять множество всех чисел от \(0\) до \(99\), кроме числа \(1\).