-->
当前位置:首页 > 题库

PROGRAMMING:Xiaoyu's army

Luz5年前 (2021-05-10)题库476
Xiaoyu, who has just experienced the battle of fawn, is very happy, because Xiaoyu used only tens of thousands of troops to annihilate the enemy's 400000 troops
But Xiaoyu also feels very sad, after all, not every time can be so lucky. So Xiaoyu wants to recruit an army again
There are now $$n $$soldiers and $$M $$leadership relationships, such as $$A1 $$- > $$B1 $$, $$A2 $$- > $$B2 $$, $$am $$- > $$BM $$. Where $$AI $$$$Bi $$means that soldiers $$AI $$lead soldiers $$Bi $$
The $$M $$relationship guarantees that there are no double edges and that it is a $$DAG $$
An army begins with a person of the highest rank (i.e. he has no leader) and ends with a person of the lowest rank (i.e. he has no leader)
Now Xiaoyu wants to know how many such troops there are
###Input format:
In the first line, two positive integers $$n $$and $$M $$indicate that there are $$n $$soldiers and $$M $$leader relationships
Next, there are two positive integers, $$AI $$and $$Bi $$in each line of the $$M $$line, indicating that soldier $$AI $$leads soldier $$Bi $$(guarantee 1 < = $$AI $$, $$Bi $$< = $$n $$)
1<=$$n$$<=1000000,1<=$$m$$<=2000000.
A single person cannot form an army
###Output format:
Output an integer to represent how many troops there are. Because the answer may be too large, the answer needs to take the module of $$1e9 + 7 $
###Input example:
Here is a set of inputs. For example:
```in
5 6
1 3
1 4
2 3
2 4
3 5
4 5
```
###Output example:
The corresponding output is given here. For example:
```out
four
```







answer:If there is no answer, please comment