题目背景

神奇的跳蚤马戏团 Nehryzma 来到了城里。

舞台上有 $N$ 个标记点，编号为 $0$ 到 $N-1$。最初，每个标记点上恰好有一只跳蚤，且从 $i$ 号点出发的跳蚤编号也是 $i$。

训练师事先在舞台上画了 $N$ 条箭头。每个标记点恰好有一条箭头从它出发，也恰好有一条箭头指向它；箭头允许指向原点自身。每当训练师发出一次口令，所有跳蚤都会沿所在点的出箭头同时跳到下一个点。由于每个点恰好有一条入箭头，跳跃结束后仍然每个点上恰好有一只跳蚤。

正式演出时，箭头已经被擦掉。观众 Julka 只看清了第四次跳跃后的状态。请你根据她观察到的结果，计算舞台上原本可能画有多少种箭头配置。

题目描述

给定一个长度为 $N$ 的排列 $S$。对于每个 $i$，$S_i$ 表示编号为 $i$ 的跳蚤在连续跳跃四次之后所在的标记点。

你需要统计满足上述观察结果的箭头配置数量。

更形式化地，设 $f(x)$ 表示从标记点 $x$ 出发的箭头指向的标记点。由于每个点的入度和出度都恰好为 $1$，$f$ 是一个排列。题目要求统计满足

$$f(f(f(f(i))))=S_i\qquad(0\le i<N)$$

的排列 $f$ 的数量。

答案可能很大，请对 $1\,000\,000\,009$ 取模。

若不存在满足条件的箭头配置，输出 $0$。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $S_0,S_1,\ldots,S_{N-1}$。

输出格式

输出一个整数，表示满足条件的箭头配置数量对 $1\,000\,000\,009$ 取模后的结果。

数据范围

• $1\le N\le 652$；
• $0\le S_i<N$；
• $S_0,S_1,\ldots,S_{N-1}$ 两两不同。

样例 1

输入

4
1 2 0 3

输出

1

解释

唯一可能的箭头配置为

$$0\to1,\qquad1\to2,\qquad2\to0,\qquad3\to3.$$

四只跳蚤的轨迹分别为：

• 跳蚤 $0$：$0\to1\to2\to0\to1$；
• 跳蚤 $1$：$1\to2\to0\to1\to2$；
• 跳蚤 $2$：$2\to0\to1\to2\to0$；
• 跳蚤 $3$：始终停留在 $3$ 号点。

样例 2

输入

3
0 1 2

输出

4

解释

可以让三只跳蚤始终原地跳，也可以任选一只原地跳、另外两只每次交换位置，因此共有 $1+3=4$ 种配置。

样例 3

输入

6
0 1 2 3 5 4

输出

0

样例 4

输入

8
1 0 7 5 6 3 4 2

输出

48