CF15E Triangles

去年夏天，Peter 在位于乡下的奶奶家中时，附近的森林里又狼袭击了羊群。于是他现在害怕森林，绕着森林走，甚至不敢出家门。但他将这归为这片森林有一种在他看来很奇怪的模式。这个森林有 $n$ 层，$n$ 为偶数。 你得到了一张地图，其中 H 点是 Peter 的奶奶家，森林比较茂密的部分用灰色标注（具体可以见[下图](https://espresso.codeforces.com/92989409c771b378af1cd21276749b747a7748aa.png)）。  漫长的缓和后，Peter 终于听从了奶奶的劝说，决定出门走走，呼吸新鲜空气。谨慎起见，Peter 提前在家规划好了路径。他认为最合适的路径有以下特征： - 起点和终点相同，即都是奶奶家； - 只沿着林中小径走（即图中的黑线）； - 路线长度是正数（不然怎么呼吸新鲜空气）； - 路线不能自己相交； - 路线围成的区域内森林都不能太茂密（即不能有灰色）； 请求出最合适的有向路线的数量，对 $10^9+9$ 取模。

输入数据包含且仅包含一个正整偶数 $n$（$2\le n \le 10^6$）。

输出唯一的整数：最合适的路线数量对