← 返回题目列表

Codeforces · 238/A

A. 不是羊毛序列

中文机器翻译题面 查看原题

长度为 n 的非负整数 a1, a2, ..., an 序列称为羊毛序列当且仅当存在两个整数 l 和 r (1 ≤ l ≤ r ≤ n) 使得 $$a_{l} \oplus a_{l+1} \oplus \cdots \oplus a_{r} = 0$$。换句话说,每个羊毛序列包含异或等于 0 的连续元素的子序列。

表达式 $$x \oplus y$$ 表示对数字 x 和 y 应用按位异或运算。给定的操作存在于所有现代编程语言中,例如,在 C++ 和 Java 语言中,它被标记为“^”,在 Pascal 中被标记为“xor”。

在此问题中,要求您计算由 0 到 2m - 1 之间的 n 个整数组成的非羊毛序列的序列数。您应该打印这个数字模 1000000009 (109 + 9)。

输入

输入的唯一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 105)。

输出

在唯一的输出行上打印所需的序列数模 1000000009 (109 + 9)。

示例

输入 #1

3 2

输出 #1

6

注意

由整数 0、1、2 和 3 组成的非羊毛序列的长度为 3 的序列为 (1, 3, 1)、(1, 2, 1)、(2, 1, 2)、(2, 3, 2)、(3, 1, 3) 和 (3, 2, 3)。