CommutativeMapping | Topcoder Archive

Problem Statement

As a birthday present from Snimda, bear Limak received two arrays f and g with the same length N. All elements in both f and g were between 0 and N-1, inclusive. It was some time ago and Limak doesn't remember array g now!

Though he does remember one thing. f[g[i]] = g[f[i]] was true for all i between 0 and N-1, inclusive.

How many arrays g satisfy the above condition? Help Limak and count them! Return the answer modulo 1,000,000,007.

Definition

Class:: CommutativeMapping
Method:: count
Parameters:: int[]
Returns:: int
Method signature:: int count(int[] f)
(be sure your method is public)

Constraints

f will contain between 1 and 2,000 elements, inclusive.
Each element in f will be between 0 and (|f|-1), inclusive.

Examples

```
{0,0,0,0}
```
```
Returns: 64
```
We have f[g[i]] = 0, g[f[i]] = g[0]. So we need g[0] = 0. For i = 1,2,3, g[i] can be anything in {0,1,2,3}, we have 4^3 = 64 solutions.
```
{0,1,2,3,4,5,6,7,8,9}
```
```
Returns: 999999937
```
In this case all g satisfy the condition, so the answer is (10^10)%(10^9+7).
```
{1,2,3,0}
```
```
Returns: 4
```
The following four arrays can be g: {0,1,2,3}, {1,2,3,0}, {2,3,0,1}, {3,0,1,2}.

{8,5,5,15,17,1,5,8,16,7,17,4,0,7,15,9,12,2,0,16,11,16,11,16,10,16,2,14,0,10,15,1,9,16,14,7,4,10,4,0,1,9,15,1,8,17,1,16,9,15,17,7,14,7,4,3,14,7}

Returns: 980600184

```
{0}
```
```
Returns: 1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.