H. Hierarchy Mess
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Institute of Multiple Echelons, commonly referred to as IME, has plenty of staff and students, all of whom are forced to follow a strict hierarchical order. The leader of the institute, known as the commander, has no idea how the system works below him, as he's on top of the food chain and so it's nothing for him to worry about. One fine day, when he finally dared to look down, the commander uncovered the complete hierarchical map of his institute. It is a giant web of people with numerous ways for information to reach him.

He became interested in this map, and came up with the following inquiry: how many different ways exist for information to reach him, starting from any person within IME. Information is able to reach him the following way: the person who needs to pass something to the commander passes it to his/her superior, who then passes it on to his/her superior, and so on until it reaches the commander. If a person tries to send some information to the commander, it is impossible for that information to return to the sender somehow.

Of course, since he's the commander, he delegates this task to you. He presents to you the map, consisting of $$$n$$$ people and $$$m$$$ hierarchical relationships. Each relationship describes two people, $$$a$$$ and $$$b$$$, in which $$$b$$$ is a subordinate of $$$a$$$. It is guaranteed that the commander's ID is 1, that he isn't anyone's subordinate and that anyone is able to reach him.

Input

The first line of the input consists of two integers, $$$n$$$, $$$m$$$ $$$(1 \leq n \leq 10^5)$$$ $$$(n - 1 \leq m \leq \min (10^6, \frac{n \times (n - 1)}{2})$$$ — the amount of people in the institute and the amount of relationships described in the map.

The next $$$m$$$ lines describe the relationships, each line consists of two integers, $$$a$$$, $$$b$$$ $$$(1 \leq a, b \leq n)$$$ — indicating that the person with ID $$$b$$$ is a subordinate of the person with ID $$$a$$$. It is guaranteed that $$$b$$$ isn't $$$1$$$ and that for every relationship $$$(a, b)$$$, it is impossible for information starting at $$$a$$$ to end up with the person $$$b$$$.

Output

Print a single integer — the number of ways information is able to reach the commander starting from any person. Since this number can be very large, print it out modulo $$$998244353$$$.

Example
Input
5 7
1 2
2 3
2 5
5 3
3 4
1 5
5 4
Output
11
Note

For the sample input it is easy to see that the following paths are possible for info to travel through:

4 - 5 - 1

4 - 5 - 2 - 1

4 - 3 - 2 - 1

2 - 1

5 - 2 - 1

4 - 3 - 5 - 1

3 - 2 - 1

4 - 3 - 5 - 2 - 1

3 - 5 - 1

3 - 5 - 2 - 1

5 - 1