Heavy Chain Decomposition

A rooted tree with n nodes (labeled 1, 2, …, n) is given. For any node u in the tree, define its height h_u as follows:

• If u is a leaf, then h_u = 1.
• If u is an internal node with children from the set S_u, then
  h_u = max_{v ∈ Su}(h_v) + 1.

For each non‐leaf node u it is required that exactly one of its children v satisfies

h_v + 1 = h_u and t_v = t_u

and all the other children w satisfy t_w = w. Here the array t[1…n] is the result of the so–called long–chain (heavy chain) decomposition defined as follows:

For the root r we must have t[r] = r. Then, if a node u is not the root and if it is chosen as the heavy child of its parent then we set t[u] = t[parent(u)], and if it is not chosen (i.e. it is a light child) then t[u] = u.

Given an array t[1…n], count how many different trees (with labeled nodes and with root 1) have a heavy chain decomposition equal to the given t array. Two trees are considered different if their root is different or their sets of edges differ. Since the answer can be very large, output it modulo the prime 20051131.

Note: It is guaranteed that there is at least one tree whose heavy chain decomposition equals the given array (although the answer modulo 20051131 might be 0).

---

Input Format:
The first line contains a single integer n (number of nodes).
The second line contains n space–separated integers t[1], t[2], …, t[n].

Output Format:
Output a single integer – the number of trees satisfying the given heavy chain decomposition conditions, modulo 20051131.

---

Explanation:
For example, consider the following two cases:

1. Case 1: n = 1, t = [1]. This tree is just a single node, and the answer is 1.
2. Case 2: n = 3, t = [1, 1, 1]. One valid tree is the chain 1 → 2 → 3. In this tree, for node 1 the only child 2 is forced to be the heavy child (since h(2)+1 = h(1)); similarly, node 2’s only child 3 is heavy. The heavy chain decomposition is t[1]=1, t[2]=1, t[3]=1. The answer in this case is also 1.

It is possible that for other tree structures (for instance, when a node has several children that are candidates for the heavy edge) there are several valid heavy–child assignments giving rise to the same t array. Your task is to count over both tree structures and heavy–child choices.

inputFormat

The first line contains an integer n (n ≤ 10).

The second line contains n space–separated integers representing the array t[1…n].

It is guaranteed that there is at least one tree whose heavy chain decomposition equals the given array.

outputFormat

Output a single integer – the total number of trees (over all tree structures and heavy–child choices) that yield the given heavy chain decomposition, modulo 20051131.

sample

1
1

1