All About Mod 1000000007

I recently finished a problem on Codechef that had a statement like this in it:

Take the result and mod the result by 1000000007.

Why do we do this?

In Java, an integer’s maximum value is 2^31-1, or 2,147,483,647. That is obviously bigger than 1,000,000,007.

In Java, a long’s maximum value is 9,223,372,036,854,775,807!

If we look at the 88th Fibonacci number, we will overflow a long with a value of 1,100,087,778,366,101,931.

If we have an algorithm problem that suggests we mod the result, that means we can mod the numbers as we operate on them.

Addition

Let’s consider a simple example with a maximum value of 10. We don’t want to overflow the number 10, so we need a prime number a little less than 10, so let’s pick 7.

We might try to do something like this:

(1 % 7) + (2 % 7) = 3.

This seems to be the same as if we had done:

1 + 2 = (3 % 7).

Seems logical. If we add the two numbers and mod the result, it’s the same as if we had modded each number separately and then added those results.

This was my approach to a recent algorithm problem and I eventually realized that this could happen:

(5 % 7) + (6 % 7) = 11.

Not quite the same as:

5 + 6 = (11 % 7) – which is of course not true.

The reason is that at some point the sum should exceed the number we are modding by and so the sum of two numbers should be modded, not the individual numbers.

The number 1000000007 is special in the regard that any sum that is modded by 1000000007 will stay below the maximum value of an integer.

You can calculate Fibonacci numbers and always mod the result by 1000000007 and you will never overflow an integer.

All About Mod 1000000007