성냥개비로 삼각형 만들기

길이가 모두 같은 성냥개비가 여러 개 있다. 모든 성냥개비를 평면에 놓아 하나의 삼각형을 만들려고 한다.

삼각형의 한 변은 성냥개비 여러 개를 일직선으로 이어서 만들 수 있다. 그러나 성냥개비를 꺾거나 잘라서 한 변의 일부로 사용할 수는 없다.

성냥개비의 개수가 주어졌을 때, 모든 성냥개비를 사용해 만들 수 있는 서로 다른 삼각형의 개수를 구하라. 서로 합동인 삼각형은 같은 삼각형으로 센다.

성냥개비 9개로 만들 수 있는 서로 다른 삼각형은 다음 그림처럼 3가지이다.

그림 1

주의할 점은 다음과 같다.

1. 주어진 성냥개비는 모두 사용해야 하며, 삼각형은 하나만 만든다.
2. 만들 수 있는 삼각형이 없으면 0을 출력한다. 성냥개비가 1개, 2개, 또는 4개인 경우가 여기에 해당한다.
3. 서로 합동인 삼각형은 같은 삼각형으로 본다. 예를 들어 성냥개비 5개로 만들 수 있는 다음 두 삼각형은 같은 삼각형이다.

그림 2

첫째 줄에 성냥개비의 개수 n이 주어진다.

1 <= n <= 50,000

첫째 줄에 만들 수 있는 서로 다른 삼각형의 개수를 출력한다.