题目描述

Bajtazar 的谷仓里有 $n$ 个装土豆的袋子，编号 $1$ 到 $n$。一些袋子可以装在另一些袋子里面。

一次操作如下：

1. 从当前放在地板上的袋子中选择一个袋子；
2. 把这个袋子“翻过来”：原来直接装在它里面的袋子全部取出并放到地板上；
3. 将此前地板上除被选袋子以外的所有其他袋子全部装进被选袋子中。

Bajtazar 可以重复进行上述操作。求从初始状态出发，一共能得到多少种不同的袋子嵌套配置。

一个配置可以唯一地表示为：对每个袋子说明它是在地板上，还是直接装在哪一个袋子中。

输入格式

第一行一个整数 $n$，$1\le n\le16$。

接下来 $n$ 行，第 $i$ 行给出一个整数 $a_i$，满足 $0\le a_i<i$：

• $a_i=0$ 表示袋子 $i$ 放在地板上；
• 否则表示袋子 $i$ 直接装在袋子 $a_i$ 中。

输出格式

输出一个整数，表示可达的不同配置数量，对 $10^9+7$ 取模。

样例输入

2
0
1

样例输出

3