CF1679F Formalism for Formalism

Yura is a mathematician, and his cognition of the world is so absolute as if he have been solving formal problems a hundred of trillions of billions of years. This problem is just that! Consider all non-negative integers from the interval $ [0, 10^{n}) $ . For convenience we complement all numbers with leading zeros in such way that each number from the given interval consists of exactly $ n $ decimal digits. You are given a set of pairs $ (u_i, v_i) $ , where $ u_i $ and $ v_i $ are distinct decimal digits from $ 0 $ to $ 9 $ . Consider a number $ x $ consisting of $ n $ digits. We will enumerate all digits from left to right and denote them as $ d_1, d_2, \ldots, d_n $ . In one operation you can swap digits $ d_i $ and $ d_{i + 1} $ if and only if there is a pair $ (u_j, v_j) $ in the set such that at least one of the following conditions is satisfied: 1. $ d_i = u_j $ and $ d_{i + 1} = v_j $ , 2. $ d_i = v_j $ and $ d_{i + 1} = u_j $ . We will call the numbers $ x $ and $ y $ , consisting of $ n $ digits, equivalent if the number $ x $ can be transformed into the number $ y $ using some number of operations described above. In particular, every number is considered equivalent to itself. You are given an integer $ n $ and a set of $ m $ pairs of digits $ (u_i, v_i) $ . You have to find the maximum integer $ k $ such that there exists a set of integers $ x_1, x_2, \ldots, x_k $ ( $ 0 \le x_i < 10^{n} $ ) such that for each $ 1 \le i < j \le k $ the number $ x_i $ is not equivalent to the number $ x_j $ .

The first line contains an integer $ n $ ( $ 1 \le n \le 50\,000 $ ) — the number of digits in considered numbers. The second line contains an integer $ m $ ( $ 0 \le m \le 45 $ ) — the number of pairs of digits in the set. Each of the following $ m $ lines contains two digits $ u_i $ and $ v_i $ , separated with a space ( $ 0 \le u_i < v_i \le 9 $ ). It's guaranteed that all described pairs are pairwise distinct.

Print one integer — the maximum value $ k $ such that there exists a set of integers $ x_1, x_2, \ldots, x_k $ ( $ 0 \le x_i < 10^{n} $ ) such that for each $ 1 \le i < j \le k $ the number $ x_i $ is not equivalent to the number $ x_j $ . As the answer can be big enough, print the number $ k $ modulo $ 998\,244\,353 $ .

In the first example we can construct a set that contains all integers from $ 0 $ to $ 9 $ . It's easy to see that there are no two equivalent numbers in the set. In the second example there exists a unique pair of equivalent numbers: $ 01 $ and $ 10 $ . We can construct a set that contains all integers from $ 0 $ to $ 99 $ despite number $ 1 $ .