TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3817
  • Problem
  • P3817排列
    Limits : Time Limit : - MS   Memory Limit : 165536 KB
    Judgment Tips : 1000ms
    Description

    将自然数 1 到 n 任意排列,然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。

    例如:对于 1..5 的一个排列:3 2 4 1 5,可得到:3 > 2 < 4 > 1 < 5,其中有两个“>”和 2 个“<” 。

    现在给出自然数 n,问在自然数 1..n 的所有排列中,有多少个排列恰好有 k 个“<”。 请你解答这个问题。 

    Input Format

    包含多组数据。第一行一个整数 T,表示有 T 组数据。  
    每组数据的占一行,包含两个整数 n 和 k,它们之间用一个空格分开。 

    Output Format

    共 T 行,每组数据输出一行,每行一个整数,表示对应输入的排列数,这个数如果很大,则需要 输出 mod 1000000007 的结果。 

    Sample Input 1


    5 2 
    8 1 
    9 4 
    7 3

    Sample Output 1

    66
    247
    156190
    2416

    Sample Input 2

    5
    9 3
    10 2
    7 2
    8 5
    6 2

    Sample Output 2

    88234
    47840
    1191
    4293
    302

    Hint

    对于 30%的数据:n<=10
    对于 100%的数据:k<n<=1000  1<=t<=1000