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
|
sadiq252:
2021-09-12 19:05:48
Nice problem!Solved by first try,used binary exponentiation. |
|
curiousyuvi:
2021-05-28 06:33:53
ac in one go...hint: solve the equation Zn+Zn-1 -2Zn-2....: )
|
|
anchord:
2021-05-27 06:13:49
Tbh, this problem was worth of thinking, thanks for this problem, i learned so much from this:3 |
|
srivathsav1410:
2021-05-09 13:43:22
easy one ac in one go just n=5 and k=2 you will get it |
|
abuhanif:
2021-04-19 17:28:14
@sakshi_38 n is always greater than 1 see constrain 1<n<200000000 |
|
sakshi_38:
2021-02-05 07:58:40
what will be the answer when n=1? |
|
makdi:
2020-12-01 08:05:39
Be careful , wasted half an hour because it is 10^7 + 7 and not 10^9+7 |
|
aa18:
2020-10-13 18:59:24
Why recursive approach of modular exponentiation is giving WA but iterative got accepted. |
|
kishlay1105:
2020-07-26 21:29:22
Just take a pen and paper and solve the above expression , many terms will get cut and you will get a small expression which will be solved using modular exponentiation :) |
|
coolboy7:
2020-07-26 19:41:33
@ashish try to solve the expression first you will see that some terms will be cancelling |
| 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