题目描述

众所周知，一个长度为 $2n$ 的合法括号序列的方案数为 $C_n$，$C_n$ 为 Catalan 数第 $n$ 项，由简单的补集转化可以得出：

$$C_n=\dfrac{1}{n+1} \dbinom{2n}n$$

但这并不是本题要讨论的。不妨令括号序列左括号为 1，右括号为 0，则括号序列可映射到 01 序列上。

设所有长度为 $2n$ 的 01 括号序列形成的集合为 $G_n$，对于一个 01 序列 $a_i$（$1\leq i\leq 2n$），有其对应的系数序列 $a_i^\prime$（$1\leq i\leq 2n$），如下定义 $F_n$ 为：

$$F_n=\sum_{x\in G_n} \prod_{i=1}^{2n} x_i^\prime$$

由上面讨论的，显然$a_i^\prime=1$（$1\leq i\leq 2n$）时，$F_n=C_n$。

现对于每一个 01 序列 $x_i$，有：

$$x_i=\begin{cases}1&x_i=1\\2\times \sum_{1\leq k\leq i}x_k-i&x_i=0\end{cases} $$

求 $F_n\bmod p$ 的值，其中 $p=10^9+9$。

输入格式

一行，一个整数 $n$。

输出格式

一个整数表示答案。

3

15

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 10^7$。

题目来源

By 2255。