301270: CF238A. Not Wool Sequences
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Not Wool Sequences
题意翻译
一个长度为 $n$ 的非负整数序列 $a_1,a_2,\ldots,a_n$ 称为 `wool` 序列,只要存在两个整数 $l$ 和 $r$($1\leq l\leq r\leq n$)且 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF238A/2ec5f782c063d456c865928ec08f722fe4394a16.png)。换句话说,每个 `wool` 序列包含一个连续元素的子序列,其中异或值等于 $0$。 在这个问题中,我们要求您计算由 $0$ 到 $2^m - 1$ 的 $n$ 个整数组成的**非 `wool` 序列**的数目,并取模 $10^9+9$。题目描述
A sequence of non-negative integers $ a_{1},a_{2},...,a_{n} $ of length $ n $ is called a wool sequence if and only if there exists two integers $ l $ and $ r $ $ (1<=l<=r<=n) $ such that ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF238A/2ec5f782c063d456c865928ec08f722fe4394a16.png). In other words each wool sequence contains a subsequence of consecutive elements with xor equal to 0. The expression ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF238A/a0b0fe9e9428287337c0277ea02ca07fcf0a01a7.png) means applying the operation of a bitwise xor to numbers $ x $ and $ y $ . The given operation exists in all modern programming languages, for example, in languages C++ and Java it is marked as "^", in Pascal — as "xor". In this problem you are asked to compute the number of sequences made of $ n $ integers from 0 to $ 2^{m}-1 $ that are not a wool sequence. You should print this number modulo $ 1000000009 $ $ (10^{9}+9) $ .输入输出格式
输入格式
The only line of input contains two space-separated integers $ n $ and $ m $ $ (1<=n,m<=10^{5}) $ .
输出格式
Print the required number of sequences modulo $ 1000000009 $ $ (10^{9}+9) $ on the only line of output.
输入输出样例
输入样例 #1
3 2
输出样例 #1
6