6176：Function Counting

题目描述

In this problem, we count the number of function f(x) satisfies below details.
1.f: M→M, ( M={-n,-n+1,-n+2,…,-1,0,1,…,n} )
2.$\forall x∈M, f_k (x)= -x,( f_0 (x)=x,f_i= f(f_{i-1} ) (i= 1,2,…) )$
3.$\forall x∈M, |(|f(x)|-|x|)|≤2$

输入解释

The first line of input contains an integer T (1 <= T <= 100) , the number of test cases.
Each test case contains a pair of integers n, k (n * k <= $10^9$), the upper limit of the set M and degree of f.
The total sum of n * k over all test cases does not exceed 4e9.

输出解释

For each test case output the answer % 1000000007.

输入样例

输出样例

提示

If k = 1, only one function f(x) = -x exists.
If n = k = 2, two functions exist. f: (-2, -1, 0, 1, 2) -> (1, -2, 0, 2, -1) or (-1, 2, 0, -2, 1).

来自杭电HDUOJ的附加信息

Recommend

liuyiding

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2017 Multi-University Training Contest - Team 10

源链接： HDU-6176

最后修改于 2020-10-25T23:29:03+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
4000/2000MS(Java/Others)	153428/153428K(Java/Others)