### 问题描述

最近蓝桥的魔法师们发现了一座大型遗迹，遗迹中存放着一种能量石，它可以供给蓝桥镇数十年的电力。魔法师们为了解决蓝桥的能源供给问题，便想要从遗迹中带走这颗能量石。

魔法师们通过观察发现，能量石被封存在一个大型的法阵的中心，法阵四周有 $n$ 个小魔法阵，每个魔法阵附近放有一颗魔法石。只有将这些散落的魔法石，放入相对应的魔法阵，整个大法阵才会解锁。

但是，每个魔法阵上有着不同的数字，代表他们的密码。每个魔法石只能放在密码和它的编号不同的魔法阵中。也就是说，魔法石 $i$ 只能放在密码不等于 $i$ 的魔法阵中。

现在请你计算出有多少种合理的方案，可以将这 $n$ 颗魔法石放入这 $n$ 个魔法阵中，使得每一个魔法阵都有一颗魔法石，并且魔法石的顺序符合解锁宝藏的要求。

输入格式

第一行一个整数 $n$（$1\leq n \leq 20$），表示魔法石和魔法阵的数量。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$（$1\leq a_i \leq n$），表示每个魔法阵对应的密码。

输出格式

输出一个整数，表示合法的方案数。由于答案可能很大，你需要对 $10^9+7$ 取模。

样例输入

3
2 1 3

样例输出

2

数据范围

$1 \leq n \leq 2\times 10^3$，$1 \leq a_i \leq n$。

说明

在这个问题中，你代表魔法师，而魔法阵上的数字则代表它们的密码。