← 返回题目列表

Codeforces · 623/E

E. 转换顺序

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

让我们将整数序列 a1, a2, ..., an 的变换 P 定义为 b1, b2, ..., bn,其中 bi = a1 | a2|| ... | ai 对于所有 i = 1, 2, ..., n,其中 |是按位或运算。

Vasya 因此将变换 P 应用于由 1 到 2k - 1(含)的整数组成的长度为 n 的所有序列。他想知道这些序列中有多少具有这样的性质,即它们的变换是严格递增的序列。帮助他计算这个数字对 109 + 7 的模。

输入

输入的唯一行包含两个整数 n 和 k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 30 000)。

输出

打印一个整数——以 109 + 7 为模的问题的答案。

示例

输入 #1

1 2

输出 #1

3

输入 #2

2 3

输出 #2

30

输入 #3

3 3

输出 #3

48