Problem Statement

Triple Factor Mark is studying a variant of the factorial. The triple factorial of a non-negative integer N , written N!!! , is the product of every positive integer that is at most N and leaves the same remainder as N when divided by 3 : N!!! = N (N-3) (N-6) ... (x+3) * x Here x is the smallest positive integer congruent to N modulo 3 , so the chain stops at 3 when N is a multiple of 3 , at 1 when N leaves remainder 1 , and at 2 when N leaves remainder 2 . By definition 0!!! = 1 — the product is empty. Because the value grows very fast, print it modulo 10^9 + 7 . Input Format A single line containing one integer N . Output Format Print a single integer: N!!! taken modulo 10^9 + 7 . Constraints 0 <= N <= 10^7 The printed value is always in [0, 10^9 + 6] , but the intermediate product must be reduced as you go — it does not fit in any built-in integer type otherwise. Examples Example 1 Input: 10 Output: 280 Explanation: 10 leaves remainder 1 modulo 3 , so the chain is 10, 7, 4, 1