ZSUM - Just Add It
For two given integers n and k find (Zn + Zn-1 - 2Zn-2) mod 10000007, where Zn = Sn + Pn and Sn = 1k + 2k + 3k + … + nk and Pn = 11 + 22 + 33 + … + nn.
Input
There are several test cases (≤ 10000). In each case two space separated positive integers n and k are given.
For last test case n and k are given as 0 0, which is not to be processed.
Constraints
1 < n < 200000000 0 < k < 1000000
Output
For each case print the asked value in separate line.
Example
Input: 10 3 9 31 83 17 5 2 0 0 Output: 4835897 2118762 2285275 3694
hide comments
|
coolboy7:
2020-07-26 19:26:17
it's binary exponentiation
|
|
ks_r:
2020-07-23 13:08:28
AC In One GO !! :) |
|
ashish_2495:
2020-06-08 18:05:05
I am using binary exponention and got sample results but the spoj shows tle...
|
|
md_yasin:
2020-05-22 10:39:16
AC in one go!!! :v be careful to use long long and calculate power |
|
deependra_18:
2020-04-12 14:10:25
thanks @sicklesplit for pointing 1e7+7 is not a prime . |
|
izrail:
2020-04-09 17:18:45
n^k+2(n-1)^k+2(n-1)^(n-1)+n^n careful about mod and evaluate this exp. |
|
subodh898:
2019-10-28 13:44:01
just solve the final relation given in terms of n and use binary exponentiation. Also careful about the mod, it is 1e7+7. |
|
destiny_gamer:
2019-10-01 13:54:45
AC in one go! Finaally! |
|
a_l_o_n_e:
2019-08-29 16:27:05
AC in one go!!! |
|
sicklesplit:
2019-08-22 16:02:19
Reemember that 1e7+7 is not prime. |
| Added by: | Manohar Singh |
| Date: | 2011-09-04 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Manohar Singh |
RSS