삼각형만들기3 timer 1s memory 128MB

길이가 일정한 성냥개비 N개가 주어질 때 이를 이용하여 만들수 있는 삼각형의 개수는 모두 몇 가지일까?

"jungol 3278 삼각형 만들기2"를 여러분의 도움으로 아주 힘들게 해결한 정원이에게 다음과 같은 문제가 주어졌다.

성냥개비의 개수가 무려 10²⁰⁰⁰ 개 까지 입력된다고 한다.

과연 정원이는 이 문제를 풀수 있을 까?

정원이와 함께 문제를 해결해 보자.

[제약 사항]

1. 주어진 N개의 성냥개비를 모두 사용해야만 한다.

2. 만들어진 삼각형을 회전하거나 뒤집었을때 이전의 모양과 같다면 한 가지 경우로 본다.

3. 테스트 케이스 5개가 주어진다.​​