题目描述

你现在有一张n个点m条边的有向图。

请问有多少个子图（子图的定义是选定一个边集，及其包含的所有点）是没有环的？

在计算完成后，请将答案对$10^9+7$取模。

输入格式

第一行两个整数$n$和$m$代表点数和边数。

接下来$m$行每行两个整数表示一条有向边。

数据保证输入图中无重边无自环。

输出格式

输出一个整数表示答案，对 $$ 10^9+7$$ 取模。

样例1

3 6
1 2
2 1
1 3
3 1
2 3
3 2

25

数据范围

对于40%的数据$n\le 5，m\le 20$；

对于60%的数据$n\le 10$；

对于80%的数据$n\le 15$

对于100%的数据$n\le 17$。