Candy Distribution Without Consecutive Same Stacks

You are given an integer (N) representing the number of candy distribution moves and a list of (N) integers representing the candy stacks. In each move, a candy must be distributed from one of the stacks. Your task is to count the number of valid orders in which the candies can be distributed so that no two consecutive moves use the same stack. In other words, if the order of stacks used is (a_1, a_2, \dots, a_N), then for every (1 \leq i < N) it must hold that (a_i \neq a_{i+1}).

For example, when (N = 2) and the stacks are [1, 3], there are 2 valid orders. When (N = 3) and the stacks are [1, 2, 3], there are 6 valid orders (i.e. all permutations). Note that the input guarantees that the number of moves (N) equals the number of stack values provided.

Use standard input and output to solve this problem.

inputFormat

The first line contains an integer (N) indicating the number of moves. The second line contains (N) space-separated integers representing the candy stacks.

outputFormat

Output a single integer which is the number of valid distribution orders in which no two adjacent moves come from the same stack.## sample

1
1

1