CF238A Not Wool Sequences

一个长度为 $n$ 的非负整数序列 $a_{1},a_{2},...,a_{n}$ 被称为“羊毛序列”，当且仅当存在两个整数 $l$ 和 $r$，满足 $1 \leq l \leq r \leq n$，使得下列式子成立：  换句话说，每一个羊毛序列都包含一个连续子序列，其所有元素按位异或的结果等于 $0$。 表达式  表示对数字 $x$ 和 $y$ 进行按位异或运算。在所有现代编程语言中都有该运算，例如在 C++ 和 Java 语言中用符号“^”表示，在 Pascal 语言中用“xor”表示。 本题要求你计算，由 $n$ 个整数组成，每个整数的取值范围从 $0$ 到 $2^{m}-1$ 的所有序列中，不是羊毛序列的序列数。你应该输出该数量对 $1000000009$（$10^{9}+9$）取模的结果。

输入包含一行，包含用空格分隔的两个整数 $n$ 和 $m$，$1 \leq n, m \leq 10^{5}$。

输出一行，表示满足条件的序列数量对 $1000000009$ 取模后的结果。

由整数 $0$、$1$、$2$ 和 $3$ 组成的长度为 $3$ 的、不是羊毛序列的序列有： (1, 3, 1)、(1, 2, 1)、(2, 1, 2)、(2, 3, 2)、(3, 1, 3) 和 (3, 2, 3)。 由 ChatGPT 5 翻译