题目描述

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

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

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

输入格式

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

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

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

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

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

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

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

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