#P3077. Graph

Graph

Graph

题目描述

给定整数 kk。把集合 {1,2,…,2k−1}\{1,2,\dots,2k-1\} 的每个大小恰为 k−1k-1 的子集视为一个顶点。如果两个子集不相交就在它们对应的顶点之间连一条无向边,每条边的长度为 11。

两点间的距离是连接它们的最短路径的长度。求所有点对中最大的距离,并统计距离恰为该最大值的有序点对数量。不同顶点 u,vu,v 对应的 (u,v)(u,v) 和 (v,u)(v,u) 分别计数。

输入格式

第一行包含测试组数 TT(1≤T≤251\le T\le25)。接下来 TT 行,每行包含整数 kk(2≤k≤1052\le k\le10^5)。

输出格式

对每组数据输出一行两个整数,依次为最大距离和相应有序点对数。两个数均对 109+710^9+7 取模。

样例

1
3
2 60

题面存档