← 返回题目列表

Codeforces · 15/E

E. 三角形

中文机器翻译题面 查看原题

去年夏天,彼得在乡下的奶奶家,一只狼袭击了附近森林里的羊。现在他害怕穿过森林,绕着森林走,甚至不敢走出房子。他解释这一点的原因不是对狼的恐惧,而是他认为森林有 n 层的奇怪模式,其中 n 是偶数。

在地方议会中,你会得到一张区域地图,其中奶奶的房子用H点标记,茂密森林的部分标记为灰色(看图可以更好地理解)。

在家呆了很长一段时间后,彼得决定屈服于奶奶的劝说,出去呼吸新鲜空气。出于谨慎,彼得提前计划了路线。 Peter认为最合适的路线具有以下特点:

- 它在同一个地方开始和结束——奶奶的房子;
- 路线仅沿着森林小路(这些是图中标记为黑色的路段);
- 路线长度为正(为了呼吸新鲜空气,Peter 无论如何都必须走一段距离);
- 路线不能穿越自身;
- 该路线标记的部分内不应有任何茂密的森林;

您应该找到此类适合的定向路线模 1000000009 的数量。

图中给出了 n = 12 的区域图示例。由于该映射具有规则的结构,因此您可以通过示例来类推其他n。

输入

输入数据仅包含偶数 n (2 ≤ n ≤ 106)。

输出

输出唯一的数字——Peter 的路线数量对 1000000009 取模。

示例

输入 #1

2

输出 #1

10

输入 #2

4

输出 #2

74