题目背景

⊕ 代表异或运算，运算规则为：

当只有一位比特参与运算时，0⊕0=0，0⊕1=1，1⊕0=1，1⊕1=0（相同为0，相异为1）；

当有多位比特参与运算时，对每位比特分别取异或运算，如0101⊕1011=1110；

题目描述

给定一个正整数 n，求 0 到 2ⁿ−1 中有多少个数 x 满足以下方程：

x⊕2x⊕3x=0

由于满足条件的 x 可能很多，请将方案数对 10⁹+9 取模。

输入格式

单个正整数：表示 n。

输出格式

单个自然数：表示方案数对 10⁹ 取模的余数。

数据范围

对于 50% 的数据，1≤n≤10；

对于 100% 的数据，1≤n≤100000。

样例数据

输入:

3

输出:

5

说明:

满足方程的数字有：000，001，010，100，101