游客 注册 | 登录
中文 | En

3936 - Poker and Power Sum

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

TeStatic and Moat played poker at teaching building 9 yesterday for a whole night. As the result of it, TeStatic owed Moat 1024 yuan. TeStatic can't pay it back, so he asks Sheath for help.

Just in time, Sheath is puzzled by a problem about power sum, so he is willing to lending TeStatic 1024 yuan if TeStatic can solve his problem.

Sheath let ps(k,n) be the sum of the power of the first n positive integers. and the number of k -combinations of a set with n elements is recorded as by Sheath. He'd like to find the double of the sum of the product of and ps(2j−1,n) , when j pass through the first k positive integers. 

For this value will be to large, TeStatic just need to tell Sheath the remainder when the value divided by the 9th power of 10 and 7.


I.e. Let <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-10-Frame"><span class="mrow" id="MathJax-Span-60">ps(k,n)=1^<span>k</span>+2^<span>k</span>+...+<span class="msubsup" id="MathJax-Span-81">n^<span>k</span></span></span></span> , Sheath want the following value.


<span class="MathJax_Preview"></span> 
<p class="MathJax_Display" style="text-align:center;">
	<span class="MathJax" id="MathJax-Element-11-Frame"><span class="mrow" id="MathJax-Span-85"><img alt="" src="http://tk.hustoj.com:80/attached/image/20151123/20151123002701_69049.png" /></span></span> 
</p>
<p class="MathJax_Display" style="text-align:center;">
	<span class="MathJax"><span class="mrow"><br />


</p>
<p class="MathJax_Display" style="text-align:center;">
	<span class="MathJax"><span class="mrow"><br />


</p>

题目输入

In the first line of input file, there's a positive integer T indicating how much data sets will be included.

Each of the next T lines will contains two integers k and n .

We guarantee that: 

<p class="MathJax_Display">
	<span class="MathJax" id="MathJax-Element-16-Frame"><span class="mrow" id="MathJax-Span-142">1≤T≤10</span></span> 
</p>
<p class="MathJax_Display">
	<span class="MathJax"><span class="mrow"><span class="mo" id="MathJax-Span-148"></span>1≤k,n≤1000000</span></span> 
</p>

题目输出

For each data set, a single line of output should appear. This line should take the form of "v"(ignore the quotation mark), andvis the answer that Sheath want.

输入/输出样例

输入格式

1
1 2

输出格式

12

C++解答

#include <stdio.h>

const int MOD = int(1e9) + 7;

int main()
{
  int casc;
  scanf("%d", &casc);
  for (int casi = 1; casi <= casc; casi++) {
    int n, k;
    scanf("%d %d", &k, &n);
    long long a = 1;
    long long b = 1;
    for (int i = 0; i < 2 * k; i++) {
      a = a * n % MOD;
      b = b * (n + 1) % MOD;
    }
    int res = (a + b - 1 + MOD) % MOD;
    printf("%d\n", res);
  }
  return 0;
}
请先登陆