/ Vijos / 题库 /

膜拜

膜拜

背景

十八居士的毕业典礼(4)

描述

看完小品,就到了这次晚会的一个高潮,十八居士特地邀请了3位在NOI中夺银的附中神牛,让他们表演一个节目。他们就是njn,pzy,tyt。但是同学们提议,神牛的人数太少,于是十八居士又邀请了福州一中lxx,wjx,fzgd,l+q,xly……甚至远在厦门的教主lhx。同学们对他们怀有深深地敬仰之情,所以他们要膜拜这些神牛。神牛们按实力的顺序排成一个队伍,但是众所周知,神牛的特点就是爱装菜,这些神牛排成的队伍往往不是真实的实力排序。现在已知神牛队伍的逆序对个数为m个,如(2,3,4,1)的逆序对个数为3:(2,1),(3,1),(4,1)。

所以十八居士定义p为这些神牛排列成逆序对为m的不同排列方式的个数mod 1000000007的值,而同学们膜拜神牛的次数就是2^p mod 1000000007次。

格式

输入格式

两个整数n,m。n表示神牛的个数。(n<=1000,m<=10000)

输出格式

输出一个数,表示同学们膜拜神牛的次数。

样例1

样例输入1

4 3

样例输出1

64

提示

4个神牛排成混乱序列为3的队伍的排列方式共有6种:(1,4,3,2),(2,3,4,1),(2,4,1,3),(3,1,4,2),(3,2,1,4),(4,1,2,3),所以膜拜次数为2^6=64次

来源

181818181818

信息

ID
1644
难度
7
分类
动态规划 | 其他 | 快速幂 点击显示
标签
递交数
689
已通过
139
通过率
20%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

十八居士的毕业典礼