TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3817
  • 题目
  • P3817排列
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1000ms
    问题描述

    将自然数 1 到 n 任意排列,然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。 例如:对于 1..5 的一个排列:3 2 4 1 5,可得到:3 > 2 < 4 > 1 < 5,其中有两个“>”和 2 个“<” 。 现在给出自然数 n,问在自然数 1..n 的所有排列中,有多少个排列恰好有 k 个“<”。 请你解答这个问题。 

    输入格式

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

    输出格式

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

    样例输入


    5 2 
    8 1 
    9 4 
    7 3

    样例输出

    66
    247
    156190
    2416

    提示

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