题目描述

你想组织一群朋友一起去看电影，但你的朋友是否愿意来，取决于另一个朋友是否也会来。

对于每个朋友 $X$，都恰好存在另一个朋友 $Y$，使得 $X$ 只有在 $Y$ 也来时才会来。你需要邀请一个朋友子集，使得所有被邀请的人都愿意来。没有被邀请的人不需要满足任何条件。

你不想一个人去看电影，因此被邀请的子集必须非空。

请计算有多少个不同的非空朋友子集满足条件。答案可能很大，请对 $10^9+7$ 取模。

输入格式

第一行包含一个整数 $n$，表示可能被邀请的朋友数量。

朋友编号为 $1,2,\ldots,n$。

接下来 $n$ 行，第 $x$ 行包含一个整数 $y$，表示朋友 $x$ 只有在朋友 $y$ 也来时才会来。

保证：

输出格式

输出一个整数，表示满足条件的非空邀请子集数量，对 $10^9+7$ 取模。

样例 #1

输入

4
2
3
4
3

输出

3

样例 #2

输入

5
2
3
1
5
4

输出

3

数据范围

难度复核

把每个人连向他依赖的人，得到每个点出度为 $1$ 的函数图。每个弱连通分量恰好包含一个有向环。若选中环上任意一点，必须选中整个环；挂在环上的反向树可以做“选/不选”的树形 DP。最后各弱连通分量独立相乘，并减去空集。

该题不是普通 SCC 模板，关键在于理解函数图中“闭合子集”的计数结构，并处理环与入树的组合。实现量适中，评为 CF 2300。