2045年，由羊芳斐、牛芳斐、马芳斐、欧阳芳斐四名选手组成的中国国家队在IOI2045中以7分钟的罚时之差惜败给俄罗斯国家队。尽管如此，中国队仍然顺利进入前两名，获得了UOIP（Universal Olympiad in Informatics in Planets）的参赛资格，显然，该比赛将会在UOJ（Universal Online Judge）上举行。

为了训练，他们找到了算法竞赛界的最强选手共价大爷，虽然已经四十多岁，但是仍然宝刀未老，为了训练他们，共价大爷想到了一个很高明的方法——出一道UOIP十合一，一题能顶十题做。

你——黄瓜条是这年CTSC的第五名。实际上，由于数十年前某一名高二选手的失误，之前每一年的第五名都是高二选手，且在后一年，这名选手进入国家队并将这一年的另一个高二选手挤到第五名，然后这个被挤出去的选手接下来一年也进入国家队并成功挤下了另一名高二选手，依次类推，就这样延续了数十代。正所谓冤冤相报何时了。然而，你是数十年来第一次出现的已经到了高三的第五名，因此你停止了每一年都有一名高二选手被挤出去的惨剧，正是因为你的这个卓越贡献，你通过交10亿宇宙币给宇宙计算机学会成功拿到了以E类名额参加UOIP的资格。为了训练，你也弄到了这个UOIP十合一。

显然，这个题是一个提交答案题，题意很简单，给你一张 $n$ 个点 $m$ 条边的有向图，请问有多少种方法选择边的子集（可以不选或者全选），使得不存在一个环使得该环上所有边都在这个子集中，一个环就是一条由至少一条边组成的从一个点出发回到这个点的路径。答案对 $1000000007$ 取模。

为了珍惜这次去UOIP的机会，你决定把这个题目解决。

输入格式

所以输入数据 uoip1.in~uoip10.in 见数据下载。

第一行两个整数 $n,m$，表示图的点数和边数。

接下来 $m$ 行，每行两个正整数 $x,y$，表示有一条从点 $x$ 出发连向点 $y$ 的有向弧。注意可能存在从某个点出发连向自己的有向弧，且两个点之间可能存在多条同一个方向的有向弧。

输出格式

针对给定的10个输入文件 uoip1.in~uoip10.in，你需要分别提交你的输出文件 uoip1.out~uoip10.out。

输出一行一个整数，表示满足条件的子集个数对 $1000000007$ 取模的值。

样例一

input

3 5
1 1
1 2
1 2
2 3
3 1

output

13

explanation

第一条边一旦被选择就形成了一个含有一条边的环，因此第一条边可以忽略不计，只考虑后4条边。

容易发现，选出的子集不符合条件当且仅当最后两条边均被选择，且第二条边和第三条边至少选择了一条，因此有3种方案不符合要求。

所以，答案是$2^4-3=13$。

如何检验你的输出

在目录下给出了10个检验文件 uoip1.check~uoip10.check，设正确答案（取模后）为 $x$，则相应的检验文件中存储了 $x\oplus 597855228$ 对 $181$ 取模的值（$\oplus$ 表示二进制下的异或运算），可以用来检验你的答案是否正确。

例如样例数据1的答案是 $13$，所以相应的检验文件中存储的值应该是 $90$。

注意，最终测试时，只有当你的答案和标准答案一致时才能得分。

来源

matthew99

题解

https://matthew99.blog.uoj.ac/blog/1773

下载

选手文件下载