UOJ Logo Sharp Sword 剑锋 OI

SSOI

#24. 巨神兵

统计

【问题描述】

欧贝利斯克的巨神兵很喜欢有向图,有一天他找到了一张n个点m条边的有向图。
欧贝利斯克认为一个没有环的有向图是优美的,请问这张图有多少个子图(即选定一个边集)是优美的?答案对1,000,000,007取模。

【输入格式】

第一行两个整数n和m。
接下来m行每行两个整数表示一条有向边。保证无重边无自环。

【输出格式】

一行一个整数表示答案,对1,000,000,007取模。

【输入样例1】

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

【输出样例1】

25

【时空限制】

1S
256MB
对于40%的数据n<=5,m<=20;
对于60%的数据n<=10;
对于80%的数据n<=15;
对于100%的数据n<=17。