题目描述

给定长度为$n$的序列$a_i$，现在，要求对序列进行重新排列，即不改变$a_i$的数，但改变其顺序，记重排后的序列为$a_i’$，求$\forall i\in[1,n],a_i\neq a_i’$的重排方案数。

两个方案不同，当且仅当存在一个位置$i$，其重排后的数在两个方案中不一样。

输入格式

第一行输入一个整数$n$。 第二行输入$n$个整数$a_i$。

输出格式

输出一行一个整数，表示你的答案。答案对$10^9+9$取模。

样例输入 #1

6
1 1 2 2 3 3

样例输出 #1

10

说明/提示

有$1\leq a_i\leq n\leq 2000$。