Graph

时间限制:10s      空间限制:128MB

题目描述

一个集合{1,2,3,….,2*K-1},选出其中所有大小为K-1的子集。视所有集合为点,若两个集合之间没有公共元素,则在两个集合之间连一条边,边权为1。图上两个点之间的距离定义为两个点之间的最长路长度。图的最长距离定义为所有点对中距离最大的点对的距离。给定K,询问图的最长距离以及有多少对点的距离等于图的最长距离。PS: (1,2) (2,1)算两对点。
 


输入格式

多组数据。第一行一个整数,数据组数T
接下来T行,每行一个正整数K
 


输出格式

每组数据输出一行两个整数表示答案。由于答案可能很大所以请输出Mod (10^9+7)后的值
 


样例输入

1
3
 

样例输出

2 60
 

提示

对于100%的数据,2<=N<=100000 T<=25


题目来源

没有写明来源