Answers too large to store
Many counting problems have answers far too large for a 64-bit integer. The number of strings of length 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 of length . A signed 64-bit integer stops at , about , so the count no longer fits once 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 ", where means the remainder when is divided by . CSES Bit Strings asks for the count of such strings in this way:
Count the strings of length made only of the characters 0 and 1. Print the count modulo .
The only input line holds .
Constraints
Sample · Input
3
Output
8
For the sample, , 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 the count has 301,030 decimal digits.
The direct method computes 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 and, to keep the numbers readable, the modulus 7 in place of . The top row doubles exactly. The bottom row doubles and then keeps only the remainder modulo 7:
Each entry of the bottom row is the remainder of the entry above it: , and . 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, . 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
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 . The loop makes one multiplication for each position, a million at most.
For 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.
Remainders of sums and products
The loop relied on a fact that we only checked on one example: doubling a remainder and reducing the result gives the remainder of the doubled number. Look at one step of the small case, from 16 to 32. Dividing 16 by 7 gives , and doubling both sides gives
The term became , which is still a multiple of 7, so it adds nothing to the remainder. The remainder of 32 comes from the remainder of 16 alone.
The same argument works for any sum or product. Take a modulus and two numbers, each written as a multiple of plus a remainder: and . Adding them and multiplying them out gives
In both lines everything except the last term is a multiple of . So the remainder of is the remainder of , and the remainder of is the remainder of . With , and , the remainders are and :
| Operation | Exact numbers | Remainders only |
|---|---|---|
| , remainder 0 | , remainder 0 | |
| , remainder 3 | , remainder 3 |
In code the two rules are (a + b) % m and a * b % m, applied to numbers that are already remainders. A long calculation can apply them after every step, the way the Bit Strings loop does, and it ends on the same remainder as if nothing had been reduced along the way.
Two integers and that leave the same remainder modulo are called congruent modulo , written . For example and . Congruent numbers differ by a multiple of : . We use this notation where a line of working would otherwise be full of the words "leaves the remainder".
Subtraction follows the same rule, since , with one catch: can be negative. For the remainders give .
Python's % returns a result from 0 to whenever is positive, so (2 - 5) % 7 is already 4.
Comparison and division under a modulus
Reducing throws information away, and comparison and division do not survive it.
Remainders do not keep the order of the numbers they came from: , but modulo 7 they become 1 and 6. A count asked for modulo is usually built by adding and multiplying, so reducing along the way is safe. A program that has to find the smallest or the largest of several values must compare the exact values, because their remainders can come in a different order.
Dividing remainders fails as well. , but modulo 7 the numbers 24 and 6 become 3 and 6, and is not a whole number. Division needs a different tool, the modular inverse, which has its own part later on this page.
The modulus 1,000,000,007
Bit Strings and every other problem on this page that asks for a remainder use the same modulus, , and it is chosen for two reasons.
It is small enough to multiply safely. A remainder is below , which fits in a signed 32-bit integer (the largest is 2,147,483,647), and the product of two remainders fits in a signed 64-bit integer:
Three remainders multiplied together can reach , which does not fit, so a product of several numbers is reduced after each multiplication.
It is also a prime number, and under a prime modulus we can divide by any remainder except 0, as the part on division below shows. Some problems use instead, another prime below .
Python integers do not overflow, so a program that leaves out a % still prints the right answer. It is only slower, as the 13 seconds above showed. Reducing after every multiplication keeps every number small.
Raise a number to a large power
Bit Strings needed for up to a million, and one multiplication per step was fast enough. The next problem raises the exponent to a billion and asks for 200,000 powers:
Answer questions. Each gives two integers and ; print modulo . Treat as 1.
The first line holds , and each of the next lines holds and .
Constraints
Sample · Input
3 3 4 2 8 123 123
Output
81 256 921450052
The loop from Bit Strings, with in place of 2, makes multiplications for one power. In the worst case that is
multiplications, more than three weeks of work at about simple operations a second in C++, and about ten times longer in a Python loop. We need to reach a large exponent in far fewer multiplications.
Squaring reaches a large exponent in few steps. Multiplying a power by itself doubles its exponent, , so starting from and squaring again and again gives , , , and so on. Three squarings reach the exponent 8, and thirty reach an exponent above a billion.
We work one small example by hand: , the last three digits of . Squaring 3 three times, and reducing modulo 1000 each time, gives the powers of 3 whose exponents are 1, 2, 4 and 8:
The exponent 13 is a sum of entries from the top row. In base 2, 13 is written 1101, which says that . Adding exponents multiplies powers, so
We multiply the three highlighted entries, starting from the smallest and reducing as we go:
The exact value is , which does end in 323. The plain loop would have made 12 multiplications to get there. This way took 3 squarings and 2 multiplications.
The method is called binary exponentiation, or fast power: square repeatedly to get the powers whose exponents are 1, 2, 4, 8 and so on, and multiply together the ones that the binary digits of the exponent select. The saving grows with the exponent. A billion has 30 binary digits, 13 of which are 1, so takes 29 squarings and 12 multiplications: 41 operations in place of 999,999,999.
Choose the powers yourself
The widget lists the powers of the base whose exponents are 1, 2, 4, 8 and so on, reduced by the modulus, with the exponent 1 at the bottom. Each row is the square of the row below it, and its bit is one binary digit of the exponent: set a bit to 1, and that row's exponent is added to the total and its power is multiplied into the result. The widget opens on .
Fast power in code
The function power(base, exp, mod) below returns base raised to the power exp, modulo mod. It does not build the row of squares first. One loop reads the binary digits of the exponent from the right and keeps the current square in base as it goes. The program around it answers Exponentiation.
def power(base, exp, mod):
result = 1 % mod
base %= mod
while exp > 0:
if exp % 2 == 1:
result = result * base % mod
base = base * base % mod
exp //= 2
return result
data = sys.stdin.read().split()
n = int(data[0])
MOD = 10**9 + 7
for i in range(n):
a, b = int(data[1 + 2 * i]), int(data[2 + 2 * i])
print(power(a, b, MOD))On the sample input the program prints 81, 256 and 921450052.
exp % 2 is the last binary digit of what is left of the exponent, and halving exp at the end of each turn removes that digit, so the loop sees the digits of the exponent from right to left. The variable base is squared once per turn, so during the turn for the digit worth it holds the original base raised to . When the digit is 1, that power is one of the selected ones and is multiplied into result.
result starts at 1 % mod so that the function is right even when mod is 1, where every remainder is 0. When exp is 0 the loop body does not run and the function returns 1, which is also what the problem wants for .
| Turn | exp | Last digit of exp | result after the turn | base after the turn |
|---|---|---|---|---|
| 1 | 13 | 1 | ||
| 2 | 6 | 0 | 3 | |
| 3 | 3 | 1 | , leaves 561 | |
| 4 | 1 | 1 | , leaves 323 | , leaves 721 |
After the fourth turn exp is 0 and the function returns 323, the value we found by hand. The last squaring, which produced 721, is never used. The loop does it anyway, because it squares before it finds out that no digits are left.
Python has fast power built in. With three arguments, pow(base, exp, mod) computes the same value by the same method, and the Python listings in the rest of this lesson call it.
Worked example
Step through the loop
The trace runs the same loop one binary digit at a time and opens on . Its other presets show an exponent of a billion, where 30 binary digits do the work of a billion multiplications, and the exponent 16, which is 10000 in base 2, so only one power, , goes into the result. The last preset has the exponent 0 and the modulus 1, and the function returns 0 without multiplying anything.
exp = 13 is 1101 in binary, 4 bits read from the right. Start with result = 1 and square = 3 mod 1000 = 3.
- result
- 1
Change the example input
Current result: 323
Cost of fast power
- One multiplication per step, as in Bit Strings
- For an exponent , one multiplication for each unit of it: a billion for .
- Fast power
- One turn of the loop for each binary digit of , with at most two multiplications in a turn: at most 60 for .
For Exponentiation that is well inside one second:
Deeper read: why the fast power loop is correct
Number the binary digits of the exponent from 0 at the right. After the turn that handles digit , result is the original base raised to the number formed by digits 0 to of the original exponent, and base is the original base raised to , both reduced. Before the first turn result is 1, the base raised to the power 0, since no digits have been handled, and base is the base raised to .
A turn keeps this true. If digit is 1, multiplying by the current square adds to the exponent that result stands for; if it is 0, that exponent stays as it was. Squaring base prepares the power for digit , and halving exp removes the digit just handled. When exp reaches 0 the handled digits are the whole exponent, so result is the answer.
Fast power without a modulus
Fast power does not depend on the modulus. Squaring reaches a large exponent quickly whether or not anything is reduced, and LeetCode's Pow(x, n) asks for exactly that on floating-point numbers:
Write myPow(x, n) that returns raised to the integer power . is a decimal number and may be negative.
Constraints
- or
Sample 1 · Input
x = 2.00000, n = 10
Output
1024.00000
Sample 2 · Input
x = 2.10000, n = 3
Output
9.26100
Sample 3 · Input
x = 2.00000, n = -2
Output
0.25000
The exponent can be about two billion in either direction, so multiplying by itself times is too slow, and the loop from the previous part works with the % mod removed. The new case is a negative exponent. A negative power is the reciprocal of the positive one, , so . When is negative we replace by and by , and then run the loop:
def my_pow(x, n):
if n < 0:
x, n = 1 / x, -n
result = 1.0
while n > 0:
if n % 2 == 1:
result *= x
x *= x
n //= 2
return result
print(my_pow(2.0, 10))
print(my_pow(2.0, -2))The program prints 1024.0 and 0.25.
Count independent choices with powers
The second problem brings the modulus back, with an exponent far above a billion:
A string of digits is good when every digit at an even index (0, 2, 4, ...) is even and every digit at an odd index is a prime: 2, 3, 5 or 7. Leading zeros are allowed. Return how many good strings of length exist, modulo .
Constraints
Sample 1 · Input
n = 1
Output
5
Sample 2 · Input
n = 4
Output
400
Sample 3 · Input
n = 50
Output
564908303
A string of length 4 has the indices 0, 1, 2 and 3. The digits at indices 0 and 2 must be even, which leaves 5 choices for each (0, 2, 4, 6 or 8), and the digits at indices 1 and 3 must be prime, which leaves 4 choices for each (2, 3, 5 or 7). The positions are chosen independently, so the numbers of choices multiply, as they did for the bit strings: , the second sample. A string of length has even indices and odd ones, where rounds up and rounds down, so the count is
In code the two exponents are (n + 1) // 2 and n // 2:
MOD = 10**9 + 7
def count_good_numbers(n):
return pow(5, (n + 1) // 2, MOD) * pow(4, n // 2, MOD) % MOD
print(count_good_numbers(4))
print(count_good_numbers(50))The program prints 400 and 564908303, the second and third samples.
An exponent up to has at most 50 binary digits, so each of the two powers takes at most 100 multiplications.
Divide under a prime modulus
Addition, subtraction and multiplication can all be done on remainders. Division is the operation that is left, and counting formulas do contain divisions. The number of pairs that can be formed from people is , and the number of ways to choose of items divides by factorials.
Dividing two remainders does not work, as we saw: , but modulo 7 the numbers 24 and 6 become 3 and 6. The way around it is to multiply. With ordinary numbers, dividing by 6 is the same as multiplying by , the number that gives 1 when it is multiplied by 6. Modulo 7 there is a remainder with the same property. It is 6 itself, since , and multiplying by it does the work of dividing by 6:
In general, the modular inverse of modulo is the remainder with . It is written , and dividing by modulo means multiplying by . Modulo 7, every remainder from 1 to 6 has one:
The remainder 0 has no inverse, because 0 times anything is 0. This is the rule against dividing by zero, and under a modulus it covers every multiple of the modulus, since they all reduce to 0. When the modulus is not prime, other remainders have no inverse either: modulo 4, is always even and never leaves 1. When the modulus is prime, every remainder from 1 to has an inverse, as the theorem below shows by giving a formula for it.
For a small modulus we can find an inverse by trying every remainder. For that could take a billion multiplications for a single division. When the modulus is prime, a theorem gives the inverse directly.
Fermat's little theorem
Fermat's little theorem says that if is prime and is not a multiple of , then
For the exponent is 6, and the sixth power of every remainder from 1 to 6 does leave 1. For example and . The Deeper read below shows why this happens for every prime.
The theorem hands us the inverse. Splitting one factor of off the power gives , which is the definition of the inverse:
Modulo 7 it gives , the 5 under the 3 in the row above. For the exponent is about a billion, which fast power handles in 30 turns of its loop. So one inverse costs one fast power, power(a, p - 2, p).
MOD = 10**9 + 7
def inverse(a):
return pow(a, MOD - 2, MOD)
half = inverse(2)
print(half)
print(2 * half % MOD)
n = 10**9
print(n * (n - 1) // 2 % MOD)
print(n % MOD * ((n - 1) % MOD) % MOD * half % MOD)The program prints 500000004, 1, 28 and 28.
The inverse of 2 is 500,000,004, and the second line of output confirms it: , which leaves 1. The last two lines count the pairs among a billion people in two ways. The first divides the exact product by 2 and reduces afterwards. The second reduces everything first and multiplies by the inverse of 2. Both print 28, and the second way keeps working when the exact numbers are too large to store.
A program that divides by the same numbers many times should compute each inverse once and store it in a table.
Deeper read: why Fermat's little theorem holds
Take and , and multiply each of the remainders 1 to 6 by 3, reducing modulo 7:
The bottom row holds the same six remainders in another order. No value can appear in it twice. If and left the same remainder, 7 would divide . A prime that divides a product divides one of its factors, and 7 does not divide 3, so it would have to divide , which is impossible for two different numbers from 1 to 6.
Since the two rows hold the same numbers, the product of one row is congruent to the product of the other:
So 7 divides . It does not divide 720, which is a product of numbers smaller than 7, so it divides , and that is the statement . The argument used only that 7 is prime and that 3 is not a multiple of it, so it works for every prime and every that does not divide.
Reduce an exponent modulo p − 1
Fermat's theorem has a second use, for exponents that are too large to write down:
Answer questions. Each gives three integers , and ; print modulo . Treat as 1.
The first line holds , and each of the next lines holds , and .
Constraints
Sample · Input
3 3 7 1 15 2 2 3 4 5
Output
2187 50625 763327764
The exponent here is , which can have billions of digits, so we cannot compute it and pass it to fast power. It has to be reduced first, but not modulo . An exponent counts factors, and taking factors of away changes the product. Fermat's theorem says which number of factors can be taken away: , so every block of factors multiplies the result by 1. Only the remainder of the exponent modulo matters:
With and , for example, . Reducing the exponent modulo 6 gives , which also leaves 2. Reducing it modulo 7 would give , which is wrong.
In the problem the reduced exponent is itself a power, . The answer therefore takes two calls of fast power with two different moduli:
MOD = 10**9 + 7
data = sys.stdin.read().split()
n = int(data[0])
for i in range(n):
a, b, c = (int(v) for v in data[1 + 3 * i:4 + 3 * i])
print(pow(a, pow(b, c, MOD - 1), MOD))On the sample input the program prints 2187, 50625 and 763327764.
Deeper read: the base 0 in Exponentiation II
Fermat's theorem leaves out the multiples of . Every in the input is below , so the only multiple of that can be is 0, and the program still answers that case correctly. A power of 0 is 0 unless the exponent is 0, so the program is right as long as the reduced exponent, , is 0 only when itself is 0. That holds because and the second factor is prime: a positive that is a multiple of would need to be a multiple of both factors, and no up to is.
Common mistakes with remainders and powers
Reducing only at the end in C++.
- Where it breaks
- Starting at 1 and doubling a
long long100 times overflows at the 63rd doubling, long before% 1000000007runs. Signed overflow in C++ is undefined behavior, so the printed value means nothing. The correct remainder of is976371285. - The fix
- Take
% MODafter every addition and every multiplication.
Using the floating-point
math.powfor an integer answer in Python.- Where it breaks
int(math.pow(3, 40)) % 1000gives768, because a float keeps about 16 significant digits. , so the answer is801.- The fix
- Use the integer
pow(3, 40, 1000).
Reducing an exponent modulo where it should be .
- Where it breaks
- For modulo , reducing the exponent modulo before the outer power gives
911191871. The answer is871990901. - The fix
- Reduce the exponent modulo .
Recall Compute $7^{10} \bmod 13$ by hand with fast power. Which squares does it use?
Squaring and reducing modulo 13 gives , and . The exponent 10 is 1010 in base 2, which is , so the answer uses the squares for 2 and 8: .
Recall What is the inverse of 4 modulo 13, and what does $20 / 4$ become when it is computed with that inverse?
The inverse is 10, because . Fermat's formula gives the same number, . The remainder of 20 is 7, and , so the result is 5, which is .