Bracket Sequence Restoration Count

A bracket sequence is a sequence consisting only of the characters ( and ). A sequence is considered legal (or valid) if it satisfies the following rules:

1. () is a legal sequence.
2. If A is a legal sequence then (A) is also a legal sequence.
3. If A and B are legal sequences then their concatenation AB is also a legal sequence.

For a legal bracket sequence of length 2n, we define \(match_i\) to be the index (when counting from left to right, starting at 1) of the right bracket that matches the \(i\)th left bracket.

You are given a legal bracket sequence of length \(2n\) but with some uncertainty. Instead of the full sequence, you are provided with m pieces of information. The \(i\)th piece is given by two positive integers \(a_i\) and \(b_i\), which indicate the condition

[ match_{a_i} < match_{b_i} ]

That is, the right bracket that matches the \(a_i\)th left bracket must occur earlier than the right bracket that matches the \(b_i\)th left bracket.

Your task is to count the number of legal bracket sequences of length \(2n\) that satisfy all the given \(m\) conditions. Since the answer can be very large, output it modulo \(998244353\).

inputFormat

The first line contains two integers \(n\) and \(m\) (representing the number of pairs of brackets and the number of given conditions, respectively). Each of the next \(m\) lines contains two integers \(a_i\) and \(b_i\) indicating a condition \(match_{a_i} < match_{b_i}\).

It is guaranteed that the provided conditions are consistent with some legal bracket sequences.

outputFormat

Output a single integer, the number of legal bracket sequences of length \(2n\) satisfying all the conditions, taken modulo \(998244353\).

sample

1 0

1