303203: CF623E. Transforming Sequence

Memory Limit:256 MB Time Limit:7 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Transforming Sequence

题意翻译

对于一个整数序列 $\{a_1, a_2, \ldots, a_n\}$,我们定义它的变换为 $\{b_1, b_2, \ldots, b_n\}$,其中 $b_i = a_1 | a_2 | \ldots | a_i$,其中 $|$ 表示二进制按位或运算。 现在求有多少个长为 $n$ 的序列 $a$,满足 $1\leq a_i \leq 2^k - 1$,使得它的变换 $b$ 是**严格单调递增**的,对 $10^9+7$ 取模。 $1\leq n \leq 10^{18}$,$1\leq k \leq 3 \times 10^4$。

题目描述

Let's define the transformation $ P $ of a sequence of integers $ a_{1},a_{2},...,a_{n} $ as $ b_{1},b_{2},...,b_{n} $ , where $ b_{i}=a_{1} | a_{2} | ... | a_{i} $ for all $ i=1,2,...,n $ , where $ | $ is the bitwise OR operation. Vasya consequently applies the transformation $ P $ to all sequences of length $ n $ consisting of integers from $ 1 $ to $ 2^{k}-1 $ inclusive. He wants to know how many of these sequences have such property that their transformation is a strictly increasing sequence. Help him to calculate this number modulo $ 10^{9}+7 $ .

输入输出格式

输入格式


The only line of the input contains two integers $ n $ and $ k $ ( $ 1<=n<=10^{18},1<=k<=30000 $ ).

输出格式


Print a single integer — the answer to the problem modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

1 2

输出样例 #1

3

输入样例 #2

2 3

输出样例 #2

30

输入样例 #3

3 3

输出样例 #3

48

Input

题意翻译

对于一个整数序列 $\{a_1, a_2, \ldots, a_n\}$,我们定义它的变换为 $\{b_1, b_2, \ldots, b_n\}$,其中 $b_i = a_1 | a_2 | \ldots | a_i$,其中 $|$ 表示二进制按位或运算。 现在求有多少个长为 $n$ 的序列 $a$,满足 $1\leq a_i \leq 2^k - 1$,使得它的变换 $b$ 是**严格单调递增**的,对 $10^9+7$ 取模。 $1\leq n \leq 10^{18}$,$1\leq k \leq 3 \times 10^4$。

加入题单

上一题 下一题 算法标签: