该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

$\oplus$ 代表异或（xor）运算，运算规则为：

当只有一位比特参与运算时，$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⊕2x⊕3x=0

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

输入格式

单个正整数：表示 $n$。

输出格式

单个自然数：表示方案数对 $10^9+9$ 取模的余数。

3

5

样例解释 1

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

数据规模与约定

对于 $50$ 的数据，$1\leq n\leq 10$；

对于 $100$ 的数据，$1\leq n\leq 100000$。