该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

$Z$ 国家现有 $N$ 个城市，城市的序号为 $1 \dots N$。

现 $Z$ 国家规划了 $M$ 条有向道路，有向道路是指两个城市之间存在一条路径，并且只能由前城市到达后城市，反之则不可达。

现问，从城市 $1$ 到城市 $N$ 一共有多少种不同方式，可能最后答案很大，最后模 $998 \ 244 \ 353$ 输出。

Format

Input

第一行包含 $2$ 个正整数 $N,M$，为城市数与道路数量。

接下来 $M$ 行，每行 $2$ 个正整数 $x_i,y_i$，表示有一条由城市 $x_i$ 到城市 $y_i$ 的道路。

$1 \le N \le 1,000, 1 \le M\le 10^6, x_i < y_i$。

数据保证，一定不存在自环和环，但是一个城市到另外一个城市可能存在多条路径，不保证一定能从城市 $1$ 可到城市 $N$ 。

Output

一个整数，表示从城市 $1$ 到城市 $N$ 的方式数。

Samples

3 9
1 2
1 2
1 2
2 3
2 3
1 3
1 3
1 3
1 3

10