去年夏天,彼得在乡下的奶奶家,一只狼袭击了附近森林里的羊。现在他害怕穿过森林,绕着森林走,甚至不敢走出房子。他解释这一点的原因不是对狼的恐惧,而是他认为森林有 n 层的奇怪模式,其中 n 是偶数。
在地方议会中,你会得到一张区域地图,其中奶奶的房子用H点标记,茂密森林的部分标记为灰色(看图可以更好地理解)。
在家呆了很长一段时间后,彼得决定屈服于奶奶的劝说,出去呼吸新鲜空气。出于谨慎,彼得提前计划了路线。 Peter认为最合适的路线具有以下特点:
- 它在同一个地方开始和结束——奶奶的房子;
- 路线仅沿着森林小路(这些是图中标记为黑色的路段);
- 路线长度为正(为了呼吸新鲜空气,Peter 无论如何都必须走一段距离);
- 路线不能穿越自身;
- 该路线标记的部分内不应有任何茂密的森林;
您应该找到此类适合的定向路线模 1000000009 的数量。
图中给出了 n = 12 的区域图示例。由于该映射具有规则的结构,因此您可以通过示例来类推其他n。
输入
输入数据仅包含偶数 n (2 ≤ n ≤ 106)。
输出
输出唯一的数字——Peter 的路线数量对 1000000009 取模。
示例
输入 #1
2
输出 #1
10
输入 #2
4
输出 #2
74