Basics 0/103

Modular arithmetic · 1 of 2 Advanced

Modular arithmetic basics

Keep huge answers small with remainders, raise a number to a large power by repeated squaring, and divide by a prime modulus with Fermat's inverse.

4,236 words · 19 min read

Part 1 of 8 Answers too large to store

Answers too large to store

Many counting problems have answers far too large for a 64-bit integer. The number of strings of length nn made of the characters 0 and 1 is one of them. Each position holds a 0 or a 1 whatever the other positions hold, so every extra position doubles the count: there are 2 strings of length 1, 4 of length 2, 8 of length 3, and 2n2^n of length nn. A signed 64-bit integer stops at 263−12^{63} - 1, about 9.2×10189.2 \times 10^{18}, so the count no longer fits once nn reaches 63.

An answer with hundreds of thousands of digits would turn a counting problem into a problem about arithmetic on huge numbers. So problems of this kind ask instead for the remainder of the answer after division by a fixed number, called the modulus. The statement says "print the answer modulo 109+710^9 + 7", where a mod ma \bmod m means the remainder when aa is divided by mm. CSES Bit Strings asks for the count of such strings in this way:

Difficulty tier:Very Easy

Count the strings of length nn made only of the characters 0 and 1. Print the count modulo 109+710^9 + 7.

The only input line holds nn.

Constraints

  • 1≤n≤1061 \le n \le 10^6

Sample · Input

3

Output

8

For the sample, n=3n = 3, the eight strings are 000, 001, 010, 011, 100, 101, 110 and 111, and 8 is far below the modulus, so the answer is 8 itself. For n=106n = 10^6 the count 2n2^n has 301,030 decimal digits.

The direct method computes 2n2^n in full and takes the remainder once at the end.

Python can do that, because its integers grow as long as they need to. But each doubling then rewrites a number that is hundreds of thousands of digits long. On our machine a million exact doublings followed by one % took 13 seconds, against a time limit of one second.

The fix is to take the remainder after every doubling, so that the stored number never grows. We can check on a small case that this gives the same answer. Take n=5n = 5 and, to keep the numbers readable, the modulus 7 in place of 109+710^9 + 7. The top row doubles exactly. The bottom row doubles and then keeps only the remainder modulo 7:

The number under a column is how many doublings have been done. The rows differ from the third doubling on.

Each entry of the bottom row is the remainder of the entry above it: 8=1×7+18 = 1 \times 7 + 1, 16=2×7+216 = 2 \times 7 + 2 and 32=4×7+432 = 4 \times 7 + 4. The largest number the bottom row had to compute was 8, the doubled 4 before it was reduced, and it still ends on the right answer, 32 mod 7=432 \bmod 7 = 4. The program below is the same loop with the real modulus, and the part after it shows why the two rows have to agree.

Bit Strings with a running remainder

Sign up to run
MOD = 10**9 + 7

n = int(input())
ways = 1
for _ in range(n):
    ways = ways * 2 % MOD
print(ways)

On the sample input 3 the program prints 8; for 1000000 it prints 235042059.

The variable ways starts at 1, the count for the empty string, and is below the modulus at the start of every turn of the loop, so the largest number the program ever computes is about 2×1092 \times 10^9. The loop makes one multiplication for each position, a million at most.

For n=106n = 10^6 it prints 235042059 after about a twentieth of a second on the same machine.

Arithmetic done this way, where every result is replaced by its remainder modulo a fixed number, is called modular arithmetic.