#1300. 路径统计

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: jiaangk

题目描述

给定一张 个结点 条边构成的一张有向无环图,请统计从任意入度为 的点到任意出度为 的点的简单路径个数。由于结果很大,所以结果对 取模。

输入格式

第一行两个正整数 ,表示图的结点数和边数。

接下来 行,每行两个正整数 ,表示从 连向 的有向边。

输出格式

输出一行表示答案。

样例

样例输入

5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4

样例输出

5

数据范围与提示