Given $n$, let $f(E)$ denote the number of topological sorts of a directed graph with $n$ vertices and edge set $E$.

A valid topological sort of a graph with $n$ vertices is a permutation $p[1...n]$ of $1..n$ such that for every directed edge $(u, v)$ in the graph, $p[v] > p[u]$.

Given $m$ directed edges, let $T$ be the set of these $m$ edges. Calculate $\sum_{E \subseteq T} f(E)$.

Since the answer may be very large, output the answer modulo $998244353$.

Input

The first line contains two integers $n$ and $m$.

The next $m$ lines each contain two integers $u, v$ ($1 \leq u, v \leq n$), representing a directed edge $(u, v)$.

It is guaranteed that there are no multiple edges or self-loops.

Output

Output the answer modulo $998244353$.

Examples

Input 1

3 2
1 2
2 3

Output 1

13

Subtasks

$Task1~(7pts)$: $1 \leq n, m \leq 5$

$Task2~(12pts)$: $1 \leq n+m \leq 20$

$Task3~(16pts)$: $1 \leq n \leq 9$

$Task4~(17pts)$: It is guaranteed that all edges in $E$ are of the form $(i, i+1)$.

$Task5~(48pts)$: No special constraints.

For all data, $1 \leq n \leq 20$ and $0 \leq m \leq n(n-1)$.