Introduction

If you like to practice competitive programming on some website like codeforces or leetcode, maybe there is a question that you probably have come across the words like this:

Output the value module 1e9 + 7

(Problem from cses).

So why the number is 1e9 + 7? We will answer this in this post.

What is modulo?

Modulo, denoted %, is an operator that gives you the remainder when you divide a number, for example, 5 % 3 will be equal to 2 instead of 1.

This is a basic understanding, now continue to the issue.

1e9 + 7, Why?

In a modern programming language like Javascript or C++, you will probably see something wrong when you do with large integers, For example:

int a = 10000000000;
int b = 10000000000;
int sum = a + b;

If you run this code and print it in the console, you can get a result like this: -1474836480.

That's an integer overflow, which happens when the answer of the input is too large to fit into type, so we need to its remainder to check.

If you have numbers A and B, you can do something like this:

(A + B) % modulo = (A % B + B % modulo) % modulo

(A - B) % modulo = (A % modulo - B % modulo) % modulo

(A ** B) % modulo = ((A % modulo) \ B) % modulo

Now, if you aren't familiar with it, maybe you have a question in mind, why?

If we do something like in the left expression, you still have an error for integer overflow, to avoid this, we must modulo for each element first and then do a calculus after.

Also, when we modulo the result to N, it should have some criteria:

• First, It must be not too large to fit the integer type.

• Second, it should be a prime number. After all, when we mod a prime number, it is usually different for many numbers compared with modulo it to a non-prime number because it can have two numbers with the same remainder.

A number like 1e9 + 7 fits the two conditions above because it's large enough to fit integer type, and it's a prime number.

Conclusion

Now you should have an answer to the question that we get in the title. If you have any questions, you can post them in the comments section, and we will discuss them there.