题解

题面描述

给定两个整数 $n$ 和 $k$，要求构造一个长度为 $n$ 的数组 $[a_1,a_2,\dots,a_n]$，满足：

1. 每个元素满足 $0 \le a_i < 2^k$；
2. 数组所有元素的异或和 $\oplus_{i=1}^{n} a_i$ 小于等于所有元素的与和 $\&_{i=1}^{n} a_i$。

要求统计满足条件的数组方案数，并对 $10^9+7$ 取模。

思路分析

题目内容

小红希望你构造一个长度为$n$的数组,满足:

$1$.数组中的每个元素$a$满足$0≤a_i<2^k$

$2$.数组所有元素的异或和小于等于所有元素的与和。即

$a_1 \oplus a_2 \oplus ...a_n$≤$a_1$&$a_2$&$...$&$a_n$

小红想知道有多少种可能的方案数。

输入描述

第一行输入两个整数$n$和$k$。

$1≤n≤10^5$

$0≤k≤10^5$

输出描述

输出一个整数，表示满足条件的数组的方案数。由于答案可能很大，请对$10^9+7$取模。

样例1

输入

2 2

输出

6

说明

一共有$6$种可能的方案数。分别是 $[0,0],[1,1], [2,2], [3, 3],[2, 3], [3, 2]$。