Modulo 10^9 +7

Why are we ask to take modulo 10^9 + 7 (1000000007) in many problems?
What is the arithmetic logic behind it can anyone clear it out?



The above operation guarentees that the result after operation fits in integer data type i.e it makes sure that there is no over flow in result

1 Like

Quoting Anton Lunyov,

It is the first 10-digital prime number. In some of such problems to compute the result modular inverses are needed and it helps very much that this number is prime. Also this number should be large enough since otherwise modular inverses technique may fail in some situations.

In fact any prime number less then 2^30 will be fine in order to prevent possible overflows. But this one can be easily written as 10^9+7.

This reasoning almost uniquely determined this number :slight_smile:

What’s significant about the number choice 1000000007?


you can get more varied results in modulo operation by taking modulo with large numbers and even more varied if the number is prime. so 10^9 + 7 fits well in this category and this allows tester to be sure to get large range of outputs which is less likely if number is not prime.

can someone give more particular example please ?
like for 7500 what should I display?

As it is the first ten digit prime number and can be suitable to store in 32 bits so it is easy to perform multiplications when the variable is less than 32 bits.

link :

^Give it a look :slight_smile:

you need to display “7500 % 1000000007”