### 问题描述 小蓝最近学习了阶乘，于是他定义一个新函数 $f(n)$。 $$ f(n) = \prod _{i=1} ^n i^{n-i} = 1^{n-1} \times 2^{n-2} \times 3^{n-3} \cdots \times n^0 $$ 现在小蓝随便给你一个数 $n$，请你计算一下 $f(n)$ 为多少？ 由于答案可能很大，请你对 $10^9+9$ 取模。 ### 输入格式 一个整数 $n$。 ### 输出格式 一个整数，代表 $f(n)$，由于答案可能很大，请你对 $10^9+9$ 取模。 ### 样例输入 ``` 3 ``` ### 样例输出 ``` 2 ``` ### 评测数据范围 $1 \le n \le 10^3$。