PROBLEM LINK:Author: Anton Lunyov DIFFICULTY:SIMPLE PREREQUISITES:Rule of product in combinatorics, Modulo operation PROBLEM:You are given 3 positive integers N_{1}, N_{2}, N_{3} up to 10^{18} and need to count the number of triples (X_{1}, X_{2}, X_{3}) such that 1 ≤ X_{i} ≤ N_{i} for 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_{1} * (N_{2} − 1) * (N_{3} − 2). Watch out for integer overflows during calculation of this number modulo 10^{9} + 7. EXPLANATION:If we sort numbers N_{1}, N_{2}, N_{3} the answer remains the same. Hence let's assume that N_{1} ≤ N_{2} ≤ N_{3}. Then for X_{1} we have N_{1} choices, for X_{2} we have N_{2} − 1 choices and for X_{3} we have N_{3} − 2 choices. Indeed:
Now using rule of product in combinatorics we get that the answer is simply the product of N_{1}, N_{2} − 1 and N_{3} − 2 as mentioned above. Note that when N_{2} = 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 = 10^{9} + 7 having numbers N_{i} up to 10^{18}. There are several things you should notice in order to get AC:
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[K1] and want to count the number of arrays (X[0], X[1], ..., X[K1]) such that 1 ≤ X[i] ≤ N[i] for i = 0, 1, ..., K1, 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, ..., K1. See tester's solution as a reference. ALTERNATIVE SOLUTION:The problem could be solved using inclusionexclusion principle. The formula for the answer in this case is AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:Rabbit Numbering  Topcoder SRM 463, Div I, Easy
This question is marked "community wiki".
asked 15 Jan '13, 15:00

This is also a related problem, using somewhat similar idea: PickAndDelete. answered 15 Jan '13, 15:34

@Anyone: http://www.codechef.com/viewsolution/1717274 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
1
Hi ! You should take modulo after subtraction. See i just changed this and it's accepted. http://www.codechef.com/viewsolution/1726238
(16 Jan '13, 23:45)
Thanks anuraganand, got it. Silly mistake.
(17 Jan '13, 02:00)

https://www.codechef.com/viewsolution/12397760  could anyone plz check this code and find whats the error in it?
link
This answer is marked "community wiki".
answered 04 Jan '17, 11:03

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
