1343. 异或方程
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 ⊕ 代表异或运算，运算规则为： - 当只有一位比特参与运算时，$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$ 取模的余数。 ## 数据范围 $1\le n\le 100000$ ## 输入 ```in1 3 ``` ## 输出 ```out1 5 ``` ## 提示