Count Triplet Partitionings of an Array

Given an array of numbers, your task is to count the number of ways to partition the array into triplets. A valid partition divides the entire array into groups of three elements. The ordering within each triplet and the ordering among the triplets does not matter, i.e., two partitions are considered the same if one can be obtained from the other by reordering the numbers within a triplet or reordering the triplets.

If the number of elements, n, is not divisible by 3, then the answer is 0. Otherwise, if n = 3k, the answer is given by the formula:

[ \text{Answer} = \frac{n!}{(3!)^k\cdot k!} \mod (10^9+7) ]

Print the answer modulo \(10^9+7\).

inputFormat

The first line contains a single integer n representing the number of elements in the array. The second line contains n space-separated integers representing the array elements.

Note: The values in the array do not affect the count; the answer depends only on n.

outputFormat

Output a single integer—the number of ways to partition the array into triplets modulo \(10^9+7\).

sample

3
1 2 3

1