Multiples of 3

Interview

Time limit0.1sMemory limit128 MB

Summary

Count ordered triples of multiples of 3 that add to n, with n a multiple of 3 between 3 and 3000.

Level: Medium4 of 10
Topics: Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

Yunyeong loves multiples of 3. As a hobby, he writes every natural number as a sum of three natural numbers that are multiples of 3. One day he wondered how many ways there are to write a given number as such a sum. But since this is his final semester, he has grown too lazy to do the calculation himself. So he asked you to do it.

That is, given a natural number n that is a multiple of 3, print the number of ways to write n as a sum of three natural numbers that are multiples of 3. The order of the terms matters: 12 = 3 + 6 + 3 and 12 = 3 + 3 + 6 count as different ways.

Input

A natural number n that is a multiple of 3 is given. (3 ≤ n ≤ 3000)

Output

Print the number of ways to decompose the natural number n.

Examples2

Example 1
Input
```
9
```
Expected output
```
1
```
Example 2
Input
```
12
```
Expected output
```
3
```