### PROBLEM LINK:

**Author:** Anton Lunyov

**Tester:** Hiroto Sekido

**Editorialist:** Anton Lunyov

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

Rule of product in combinatorics, Modulo operation

### PROBLEM:

You are given 3 positive integers **N _{1}**,

**N**,

_{2}**N**up to

_{3}**10**and need to count the number of triples

^{18}**(X**such that

_{1}, X_{2}, X_{3})**1 ≤ X**for

_{i}≤ N_{i}**i = 1, 2, 3**. You should output the answer modulo

**10**.

^{9}+ 7### QUICK EXPLANATION:

By sorting input numbers we can assume that **N _{1} ≤ N_{2} ≤ N_{3}**. Then the answer is

**N**. Watch out for integer overflows during calculation of this number modulo

_{1}* (N_{2}− 1) * (N_{3}− 2)**10**.

^{9}+ 7### EXPLANATION:

If we sort numbers **N _{1}**,

**N**,

_{2}**N**the answer remains the same. Hence let’s assume that

_{3}**N**. Then for

_{1}≤ N_{2}≤ N_{3}**X**we have

_{1}**N**choices, for

_{1}**X**we have

_{2}**N**choices and for

_{2}− 1**X**we have

_{3}**N**choices. Indeed:

_{3}− 2-
**X**can be any number from_{1}**1**to**N**, inclusive. There are_{1}**N**such numbers_{1} -
**X**can be any number from_{2}**1**to**N**, inclusive, which is not equal to_{2}**X**. Since_{1}**X**, there are_{1}≤ N_{1}≤ N_{2}**N**such numbers (numbers from_{2}− 1**1**to**N**, inclusive, with excluded_{2}**X**). Clearly, if_{1}**N**then the answer is zero since the only choice for_{1}= N_{2}= 1**X**and for_{1}**X**is 1, so any such triple will have equal numbers._{2} -
Finally, if

**N**then_{3}≥ 2**X**can be any number from_{3}**1**to**N**, inclusive, which is not equal to_{3}**X**and_{1}**X**. Since_{2}**X**,_{1}≤ N_{1}≤ N_{3}**X**and_{2}≤ N_{2}≤ N_{3}**X**, there are_{1}≠ X_{2}**N**such numbers (numbers from_{3}− 2**1**to**N**, inclusive, with excluded_{3}**X**and_{1}**X**)._{2}

Now using rule of product in combinatorics we get that the answer is simply the product of **N _{1}**,

**N**and

_{2}− 1**N**as mentioned above. Note that when

_{3}− 2**N**this formula also works so we don’t need to handle this case separately.

_{2}= 1Probably the trickiest part is to output the answer modulo **M = 10 ^{9} + 7** having numbers

**N**up to

_{i}**10**. There are several things you should notice in order to get AC:

^{18}-
You should use 64-bit integer type to store and input numbers

**N**._{i} -
When you want to multiply two numbers up to

**10**modulo^{18}**10**you should at first take them modulo^{9}+ 7**10**and then do the multiplication using 64-bit integer type. Otherwise the result will be wrong due to overflow. Even such code is wrong^{9}+ 7

`A % M * B % M`

since you will multiply numbers**A % M**and**B**at the second step and this will lead to overflow (**A % M**is about**1e9**and**B**is about**1e18**, so their product is about**1e27**which does not fit in 64-bit integer type). Such overflow will occur on almost every random test. -
Another common mistake is to do like that

`A = N1 % M`

`B = (N2 - 1) % M`

`C = (N3 - 2) % M`

`ans = A * B * C % M`

Here at the final step you multiply three numbers up to about**1e9**. Their product could be up to**1e27**which does not fit in 64-bit signed integer. Therefore integer overflow occurs. The correct code would be

`ans = A * B % M * C % M`

Here we take the product**A * B**modulo**M**so it becomes smaller than**M**and at the final step you multiply two numbers up to about**1e9**. Their product is up to about**1e18**and fits in 64-bit integer type. -
You can’t replace numbers

**N**by their residues modulo_{i}**10**before sorting. Indeed, the order of numbers can change after that and you get completely another number as the answer. The reference test is:^{9}+ 7`2 3 1000000008`

. Actually it happens often on any large random test. -
If after sorting you replace numbers

**N**by their residues modulo_{i}**10**and then calculate the answer as^{9}+ 7

`ans = N1 * (N2 - 1) % M * (N3 - 2) % M`

then your answer could be negative in the end. The reference test is:`1 2 1000000008`

.

Hence if you are using this method make the check

`if ans < 0 then ans = ans + M`

after that. -
As mentioned one of the ways how to do all properly is to calculate answer as follows

`ans = (N1 % M) * ((N2 - 1) % M) % M * ((N3 - 2) % M) % M`

Note that at first sight this way also could lead to negative answer. But this does not happen here. See comments in tester’s solution for explanation.

Actually, it is easy to see that this solution could be generalized to any number of variables instead of 3. Namely, if we have numbers **N[0], N[1], …, N[K-1]** and want to count the number of arrays **(X[0], X[1], …, X[K-1])** such that **1 ≤ X[i] ≤ N[i]** for **i = 0, 1, …, K-1**, and all **X[i]** are different, then after sorting numbers **N[i]** the answer will be the product of **N[i] − i** for **i = 0, 1, …, K-1**. See tester’s solution as a reference.

### ALTERNATIVE SOLUTION:

The problem could be solved using inclusion-exclusion principle. The formula for the answer in this case is

**N _{1} * N_{2} * N_{3} − min{N_{1}, N_{2}} * N_{3} − min{N_{2}, N_{3}} * N_{1} − min{N_{3}, N_{1}} * N_{2} + 2 * min{N_{1}, N_{2}, N_{3}}**.

See author’s solution as a reference. It also contains explanatory comments to this formula.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

### RELATED PROBLEMS:

Rabbit Numbering - Topcoder SRM 463, Div I, Easy

Pick And Delete - Topcoder SRM 512, Div I, Hard