You are not logged in. Please login at to post your questions!


THREEDIF - Editorial




Author: Anton Lunyov
Tester: Hiroto Sekido
Editorialist: Anton Lunyov




Rule of product in combinatorics, Modulo operation


You are given 3 positive integers N1, N2, N3 up to 1018 and need to count the number of triples (X1, X2, X3) such that 1 ≤ Xi ≤ Ni for i = 1, 2, 3. You should output the answer modulo 109 + 7.


By sorting input numbers we can assume that N1 ≤ N2 ≤ N3. Then the answer is N1 * (N2 − 1) * (N3 − 2). Watch out for integer overflows during calculation of this number modulo 109 + 7.


If we sort numbers N1, N2, N3 the answer remains the same. Hence let's assume that N1 ≤ N2 ≤ N3. Then for X1 we have N1 choices, for X2 we have N2 − 1 choices and for X3 we have N3 − 2 choices. Indeed:

  1. X1 can be any number from 1 to N1, inclusive. There are N1 such numbers :)

  2. X2 can be any number from 1 to N2, inclusive, which is not equal to X1. Since X1 ≤ N1 ≤ N2, there are N2 − 1 such numbers (numbers from 1 to N2, inclusive, with excluded X1). Clearly, if N1 = N2 = 1 then the answer is zero since the only choice for X1 and for X2 is 1, so any such triple will have equal numbers.

  3. Finally, if N3 ≥ 2 then X3 can be any number from 1 to N3, inclusive, which is not equal to X1 and X2. Since X1 ≤ N1 ≤ N3, X2 ≤ N2 ≤ N3 and X1 ≠ X2, there are N3 − 2 such numbers (numbers from 1 to N3, inclusive, with excluded X1 and X2).

Now using rule of product in combinatorics we get that the answer is simply the product of N1, N2 − 1 and N3 − 2 as mentioned above. Note that when N2 = 1 this formula also works so we don't need to handle this case separately.

Probably the trickiest part is to output the answer modulo M = 109 + 7 having numbers Ni up to 1018. There are several things you should notice in order to get AC:

  1. You should use 64-bit integer type to store and input numbers Ni.

  2. When you want to multiply two numbers up to 1018 modulo 109 + 7 you should at first take them modulo 109 + 7 and then do the multiplication using 64-bit integer type. Otherwise the result will be wrong due to overflow. Even such code is wrong
    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.

  3. 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.

  4. You can't replace numbers Ni by their residues modulo 109 + 7 before sorting. Indeed, the order of numbers can change after that and you get completely another number as the answer. The reference test is: 2 3 1000000008. Actually it happens often on any large random test.

  5. If after sorting you replace numbers Ni by their residues modulo 109 + 7 and then calculate the answer as
    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.

  6. 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.


The problem could be solved using inclusion-exclusion principle. The formula for the answer in this case is
N1 * N2 * N3 − min{N1, N2} * N3 − min{N2, N3} * N1 − min{N3, N1} * N2 + 2 * min{N1, N2, N3}.
See author's solution as a reference. It also contains explanatory comments to this formula.


Author's solution can be found here.
Tester's solution can be found here.


Rabbit Numbering - Topcoder SRM 463, Div I, Easy
Pick And Delete - Topcoder SRM 512, Div I, Hard

This question is marked "community wiki".

asked 15 Jan '13, 15:00

anton_lunyov's gravatar image

6★anton_lunyov ♦
accept rate: 12%

wikified 15 Jan '13, 15:46

This is also a related problem, using somewhat similar idea: PickAndDelete.


answered 15 Jan '13, 15:34

fushar's gravatar image

3★fushar ♦♦
accept rate: 0%

Thanks. I have added it.

(15 Jan '13, 15:39) anton_lunyov ♦6★

@Anyone: why does this code did not work? I have checked the editorial but cannot make out any reason on why it would give wrong result.


answered 16 Jan '13, 23:07

saurabheights's gravatar image

accept rate: 0%


Hi ! You should take modulo after subtraction. See i just changed this and it's accepted.

(16 Jan '13, 23:45) anuraganand5★

Thanks anuraganand, got it. Silly mistake.

(17 Jan '13, 02:00) saurabheights4★

can u plz why my code still give wa --id: 1745871


answered 23 Jan '13, 17:32

gaurav121's gravatar image

accept rate: 0%

Read paragraph 4 in editorial after the sentence
"There are several things you should notice in order to get AC:"

(23 Jan '13, 17:34) anton_lunyov ♦6★ - could anyone plz check this code and find whats the error in it?

This answer is marked "community wiki".

answered 04 Jan '17, 11:03

shatakjain2901's gravatar image

accept rate: 0%

wikified 04 Jan '17, 11:04

My doubt is the following : Just consider the case of 25 12 2012 . If I choose it without sorting, wouldn't my answer be different ? It would rather be 25 times 11 times 2010 which does not equal 12 times 24 times 2010, which is the answer obtained after sorting ?!


answered 17 May '17, 16:21

deepsnars's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 15 Jan '13, 15:00

question was seen: 14,471 times

last updated: 17 May '17, 16:21