If (a-b) < 0 then (a-b) % m fails (in C++). (cf[r]-cf[l-1]%MOD) can fail if cf[r] < (cf[l-1]%MOD).

PS: On the other hand you mentioned that the sequence is increasing (which means cf[r] > cf[l-1]). Another place why it failed can be that you need to apply MOD operation on each step, not only when printing the answer, because int overflow can occur.

in maths:(a-b)%m==(a%m-b%m)%m

In lots of programming languages, a negative number modulo something will be negative. For example, -1 mod 5 would return -1 in many languages. Since we are taking a modulo, we know x%m = (x+m)%m. Therefore, by adding mod, we always make x positive, and so our modulo should behave as expected.

For mod operation you can always do the following:

(a+b) mod m = (a+b+m)%m

So this formula will work for negative and positive values, but you have to be careful about the overflow.

Another way: If you know that a and b less than m you can apply this:

int temp = (a+b); 

if(temp >= m)temp-=m;

And this is even faster than the first formula.

First of all, I believe that your calculation of cf looked like this: cf[i] = (cf[i - 1] + f[i]) % MOD; Otherwise your solution is probably wrong, because you have integer overflow. Moreover, integer overflow in signed types (like int, but not unsigned int) is undefined behavior, that is, your program can do anything if that happen (formally, it can even wipe your hard drive). Don't worry — usually you just get strange wrong answer or runtime error.

I don't get what is the reasoning behind writing (a - b % MOD) % MOD instead of (a - b) % MOD. Would you mind explaining?

About the reference solution: you see, if we define reminder as a number from 0 to MOD - 1, then . However, it's not like some CPUs work and if you calculate in C++ on a typical PC, you will most likely get  - 2. It's correct in some sense, but it's not what "reminder" means in most problems. So, when you deal with negative numbers or subtractions modulo MOD, you should be careful be negative results. Say, writing (a - b) % MOD is unsafe even if both a and b are correct non-negative remainders, because a - b can be negative and the whole result would be wrong. However, if we write (a - b + MOD) % MOD then the whole expression on the left would be non-negative and we will get correct result (if there were no integer overflow, of course).

I've always believed that the reason a%b is negative when a is negative is that we want to maintain the invariant: a = a/b*b + a%b