Counting Valid Brick Arrangements

You are given a set of colored bricks arranged in a row. Your task is to determine the number of valid arrangements of these bricks such that no two adjacent bricks have the same color. In this problem, if there is any duplicate color in the input, then it is considered impossible to form a valid arrangement and the answer is 0. Otherwise, when all brick colors are distinct, every permutation is valid, so the answer is n! modulo \(10^9+7\), where \(n\) is the number of bricks.

Note: Input and output are handled via standard input (stdin) and standard output (stdout) respectively.

inputFormat

The first line contains an integer \(n\) representing the number of bricks. The second line contains \(n\) space-separated strings, where each string represents the color of a brick.

outputFormat

Output a single integer: the number of valid arrangements modulo \(10^9+7\). If any color appears more than once (making a valid arrangement impossible), output 0.

3
red blue green

6