CF623E Transforming Sequence

我们定义一个整数序列 $a_{1},a_{2},...,a_{n}$ 的变换 $P$ 得到序列 $b_{1},b_{2},...,b_{n}$，其中 $b_{i} = a_{1} | a_{2} | ... | a_{i}$，$|$ 表示按位或运算。 Vasya 对所有长度为 $n$ 且每个元素取值为 $1$ 到 $2^{k}-1$（包括 $1$ 和 $2^{k}-1$）的序列都进行这种变换。现在他想知道，有多少种这样的序列，使得其按照变换 $P$ 得到的序列是严格递增的。请帮他计算满足条件的序列数，结果对 $10^{9}+7$ 取模。

输入仅一行，包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^{18},\ 1 \leq k \leq 30000$）。

输出一个整数，表示满足条件的序列个数，对 $10^{9}+7$ 取模。

由 ChatGPT 5 翻译