CF1874E.Jellyfish and Hack

普及/提高-

通过率:0%

AC君温馨提醒

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

题目描述

It is well known that quick sort works by randomly selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. But Jellyfish thinks that choosing a random element is just a waste of time, so she always chooses the first element to be the pivot. The time her code needs to run can be calculated by the following pseudocode:

<pre class="verbatim"><br></br>function fun(A)<br></br>    if A.length > 0<br></br>        let L[1 ... L.length] and R[1 ... R.length] be new arrays<br></br>        L.length = R.length = 0<br></br>        for i = 2 to A.length<br></br>            if A[i] < A[1]<br></br>                L.length = L.length + 1<br></br>                L[L.length] = A[i]<br></br>            else<br></br>                R.length = R.length + 1<br></br>                R[R.length] = A[i]<br></br>        return A.length + fun(L) + fun(R)<br></br>    else<br></br>        return 0<br></br>

Now you want to show her that her code is slow. When the function fun(A)\mathrm{fun(A)} is greater than or equal to limlim , her code will get Time Limit Exceeded\text{Time Limit Exceeded} . You want to know how many distinct permutations PP of [1,2,,n][1, 2, \dots, n] satisfies fun(P)lim\mathrm{fun(P)} \geq lim . Because the answer may be large, you will only need to find the answer modulo 109+710^9+7 .

输入格式

The only line of the input contains two integers nn and limlim ( 1n2001 \leq n \leq 200 , 1lim1091 \leq lim \leq 10^9 ).

输出格式

Output the number of different permutations that satisfy the condition modulo 109+710^9+7 .

输入输出样例

  • 输入#1

    4 10

    输出#1

    8
  • 输入#2

    8 32

    输出#2

    1280

说明/提示

In the first example, P=[1,4,2,3]P = [1, 4, 2, 3] satisfies the condition, because: fun(4,[1,4,2,3])=4+fun(3,[4,2,3])=7+fun(2,[2,3])=9+fun(1,[3])=10\mathrm{fun(4, [1, 4, 2, 3]) = 4 + fun(3, [4, 2, 3]) = 7 + fun(2, [2, 3]) = 9 + fun(1, [3]) = 10}

Do remember to output the answer modulo 109+710^9+7 .

首页