울타리짓기 timer 1s memory 128MB

근면한 농부 창호는 사각형 형태의 울타리를 지어서 자신이 기르는 소들을 가두고자 한다. 

창호는 길이가 정수 N (4≤N≤2,500 )인 나무판자 한조각을 가지고 있다.

조각의 정수 위치 3점을 잡은 다음, 3개의 위치를 잘라서 조각을 길이 1이상의 네 조각으로 잘라서 사각형으로 만들고자 한다. 

네 개의 조각을 서로 이어붙였을 때 울타리의 사각형의 형태가 되어야 한다.

창호가 만들 수 있는 울타리의 개수가 몇 개인지 알아보는 프로그램을 작성하라.

주의사항:

• 자르기 위해서 잡은 3개의 위치가 다를 경우, 만들어진 조각의 크기가 같더라도 다른 경우로 간주한다.

• 사각형이 되기 위해서는 울타리의 면적이 0보다 커야 한다.

• 가능한 경우의 수는 항상 2³¹-1 이하로 나온다고 가정한다.