Background

今天下午yc请了假要去和朋友吃饭，但是晚上还要赶回来参加集训，于是在选择如何去的时候犯了难。

Description

在经过每个路口的时候都有很多选择，确保起点与终点间存在路径。

由于不会沿着道路逆行，因此每条路都是有向的；由于不会在某个地方绕圈，所以不会出现环形道路。

请帮他计算出从第一个路口到最后一个路口一共有多少条路可以走。

由于答案数据量可能会很大，请将答案对$998244353$取模。

Format

Input

第一行有两个数 $n$ 和 $m$ ，表示有 $n$ 个路口和 $m$ 条路。

接下来 $m$ 行，每行有两个数 $i$ 和 $j$ ，表示他可以从第 $i$ 个路口走到第 $j$ 个路口。

Output

输出一个数，表示他从第 $1$ 个路口走到第 $n$ 个路口有多少种选择。正确答案需要对998244353取模。

Samples

7 9
1 2
1 3
1 4
2 5
3 7
4 6
4 7
5 3
6 7

4