题目描述
$\oplus$ 代表异或运算，运算规则为：
+ 当只有一位比特参与运算时，$0\oplus0=0$，$0\oplus1=1$，$1\oplus0=1$，$1\oplus1=0$（相同为$0$，相异为$1$）；
+ 当有多位比特参与运算时，对每位比特分别取异或运算，如 $0101\oplus 1011=1110$；
给定一个正整数 $n$，求 $0$ 到 $2^n-1$ 中有多少个数 $x$ 满足以下方程：
$$x \oplus 2x \oplus 3x=0$$
由于满足条件的 $x$ 可能很多，请将方案数对 $10^9+9$ 取模。
输入
单个正整数：表示 $n$。
输出
单个自然数：表示方案数对 $10^9+9$ 取模的余数。
样例输入输出
提示
+ 对于 $50\%$ 的数据，$1\leq n\leq 10$；
+ 对于 $100\%$ 的数据，$1\leq n\leq 100000$。
样例1说明:满足方程的数字有：000，001，010，100，101