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
a_mishra4:
2017-10-25 07:28:25
solve given expression and then apply modular exponentiation on remaining terms
|
|
vishesh197:
2017-09-01 17:19:08
use modular exponentiation and now see the series carefully all n-2 terms of Zn,Zn-1,Zn-2 will get cut off while solving expression Zn+Zn-1-2*Zn-2 .good problem AC in 3rd go... |
|
kamlesh_2209:
2017-09-01 07:45:50
AC in one go use modular exponentiation....its a easy problem....
|
|
him_novice:
2017-08-31 08:57:05
JAVA--> TLE C---> Accepted in a go. Use modular exponentiaion only |
|
subhamiiit:
2017-08-24 22:14:52
my 50th on spoj.....use modular exponentation
|
|
sagnik_66:
2017-05-20 09:45:01
scanf, printf saved me :3 |
|
sagnik_66:
2017-05-20 09:45:00
scanf, printf saved me :3 |
|
amalik123:
2017-03-22 11:08:55
modular exponentiation is the key,easy one
|
|
nilabja16180:
2017-03-21 17:24:52
Modular Exponentiation don't overthink! |
|
rohit9934:
2017-03-09 18:45:21
Dont think too much,its easy.Just write one function for calculating mod.and then just write that Algebraic Expression in form of one function as a variable.Thats it.AC in 1 go after a long time.(After 1st prob :D) 0.01 sec in C. |
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 |