CF623E.Transforming Sequence

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Let's define the transformation PP of a sequence of integers a1,a2,...,ana_{1},a_{2},...,a_{n} as b1,b2,...,bnb_{1},b_{2},...,b_{n} , where bi=a1  a2  ...  aib_{i}=a_{1} | a_{2} | ... | a_{i} for all i=1,2,...,ni=1,2,...,n , where | is the bitwise OR operation.

Vasya consequently applies the transformation PP to all sequences of length nn consisting of integers from 11 to 2k12^{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 109+710^{9}+7 .

输入格式

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

输出格式

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

输入输出样例

  • 输入#1

    1 2
    

    输出#1

    3
    
  • 输入#2

    2 3
    

    输出#2

    30
    
  • 输入#3

    3 3
    

    输出#3

    48
    
首页