## Codeforces Gym - 101147G The Galactic Olympics 转

o
osc_x4rg8g6r

Discription

Altanie is a very large and strange country in Mars. People of Mars ages a lot. Some of them live for thousands of centuries!

Your old friend Foki "The president of the Martian United States of Altanie" is the oldest man on Mars. He's very old no one knows how old he is! Foki loves children, so, he had (0 < K ≤ 106) children!

The government in Altanie decided to send a team of athletes to Venus. To participate in (0 < N ≤ 103) different game in the Galactic Olympics. So Foki told them to send his children instead!

Foki is in a big problem. How can he decide whom of his children is going to participate in which game, at the same time his children must participate in all the games and every one of his children get to participate in at least one game?

Note that in a certain arrangement, each one of Foki's children can participate in multiple games in the Olympics, but each game must be arranged to exactly one player.

Your job is to help Foki and answer his question: in how many way can he arrange his children to the games in Venus Olympics while satisfying the previous two conditions.

Input

The first line of the input contains T the number of the test cases. Each test is represented with two integers on a single line. ( 0 < N ≤ 103 ) the number of the games in the Olympics, ( 0 < K ≤ 106 ) the number of Foki's children.

Output

For each test case print one line contains the answer to Foki's question. Since the answer is very large. Print the answer modulo 109 + 7

Example

Input
``13 2``
Output
``6    首先每个人至少要参加一个项目，并且一个项目最多只能属于一个人，所以我们可以很容易的建出模型: 有n个不同的物品，我们要把它们分别放入k个有序的集合，并且要求每个集合至少要有一个物品，求方案总数。    我们知道，当集合无序的时候，方案数就是 S(n,k) ，即第二类斯特林数的第n行第k列的值； 集合有序的时候，再乘上 k! 就行了。``
``````#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int ha=1000000007;
const int maxn=1005;
int T,n,m,S[maxn][maxn],jc[maxn];
inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}
inline void init(){
S[0][0]=jc[0]=1;
for(int i=1;i<=1000;i++){
jc[i]=jc[i-1]*(ll)i%ha;
}
}
int main(){
freopen("galactic.in","r",stdin);
init(),scanf("%d",&T);
while(T--) scanf("%d%d",&n,&m),printf("%d\n",n<m?0:(int)(S[n][m]*(ll)jc[m]%ha));
return 0;
}``````

`` ``
o

### osc_x4rg8g6r

CommAI-env（基于通信的人工智能环境（Environment for Communication-based AI））是一个用于训练和评估人工智能的平台。其使用了一个基于通信（communication）的设置，其中它可以通过一个...

2016/10/05
876
0

gbin1
2011/07/22
676
3
20 个新鲜的免费图标集

Free Mac Icons Theme for Retina Display or iPhone 4 Genesis Theme for iPhone 4 Genesis for iPad Icons 5 Free PSD Stickers Lamond. 70 icons Gur project Q-oob for SuperBar Build I......

2012/01/24
723
3

2012/08/29
2.6K
16
Android 日历提供器（三）

2012/10/16
745
0

osc_2fb62vw0
18分钟前
0
0

osc_eumlh0pn
19分钟前
0
0
pytest文档46-关于https请求警告问题(InsecureRequestWarning: Unverified HTTPS request is being made)

osc_8s3utzxr
20分钟前
8
0

osc_we9lokaj
21分钟前
0
0

osc_kedi1mvz
21分钟前
7
0