题目描述

塔子哥有$n$个朋友，她准备请其中一些朋友来吃饭。 其中有一些朋友有暗恋关系：假设a暗恋b，那么塔子哥带上b的时候a也必须去，否则a就会不开心。 塔子哥想知道，一共有多少种不同的请客方案可以让每个人都开心？由于答案可能过大，请对$10^9+7$取模。

输入描述

题目思路

本题难度较大，需要前置知识强连通分量。

考虑一个人u暗恋另外一个人v，则我们让v连一条有向边到u，表示u属于v的子节点，此时可以构成一个有向图。

然而有可能出现三角恋的情况，即成环，对于成环的情况，在环上只要请了任意一个人来，那环上其它所有点都必须来，所以这种情况我们可以将其缩点为一个人。

缩点需要采用强连通分量的tarjan算法，可以将环缩成一个点。