3936 - Poker and Power Sum
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>
Input
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>
Output
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.
Examples
Input
1 1 2
Output
12
Solution 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; }