题目背景

$\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$ 可能很多，请将方案数对 $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$。