Counting Ways to Form an Equilateral Triangle with Four Sticks

You are given n wooden sticks. Your task is to choose exactly 4 of them such that they can be used to form an equilateral triangle. In this problem, the intended solution is to count the number of ways to select 4 sticks (when considered as a multiset) that would allow the construction of an equilateral triangle.

It turns out that if all the sticks have the same length, any selection of 4 will always contain 3 sticks with the same length, which can form an equilateral triangle. Therefore, the answer is simply the number of combinations of 4 sticks from n, i.e.,

[ C(n, 4) = \frac{n \times (n-1) \times (n-2) \times (n-3)}{24} ]

If n < 4, then it is impossible to choose 4 sticks, and the answer is 0. Since the result can be very large, output the answer modulo \(10^9+7\).

inputFormat

The input consists of a single line containing one integer n (0 \(\leq n \leq 10^{12}\)), representing the number of wooden sticks.

outputFormat

Output a single integer, which is the number of ways to choose 4 sticks modulo \(10^9+7\).

sample

3

0