You are right, the error is in the modulo operation. “`(P + MOD - Q) % MOD`

” is guaranteed to be positive only if both `P`

and `Q`

are less than `MOD`

. But in your code, you are doing “`P += (a[i] * (start - 1)) % MOD`

”, which means that on every iteration, some value < `MOD`

is added to `P`

. So the final value of `P`

ends up being < `N`

× `MOD`

. Clearly it may not be < `MOD`

. The same applies to Q. In such a case `P + MOD - Q`

may be a negative value, which will result in a wrong answer.

There are two ways to fix this

- Change “
`P += (a[i] * (start - 1)) % MOD`

” to “`P = (P + a[i] * (start - 1)) % MOD`

”, and same for `Q`

.
- Change “
`(P + MOD - Q) % MOD`

” to “`(((P - Q) % MOD) + MOD) % MOD`

” or “`(P % MOD + MOD - Q % MOD) % MOD`

”.

Both ways make sure that the answer remains positive.