고장난 시계
시간 제한1초메모리 제한512 MB
손 세 개를 서로 다른 눈금에 놓아 끝점 삼각형을 만들 때 중심을 포함하는 삼각형 수를 2^64로 나눈 값을 구합니다.
문제
UFO가 지구에 추락한다. 외계인 선장은 추락에서 비교적 무사히 살아남지만, 그의 든든한 시계는 수리할 수 없을 정도로 망가진다.
외계인의 시계는 인간의 시계와 매우 비슷하다. 지름 30mm의 원판이고, 길이가 A, B, C 마이크로미터인 세 개의 바늘이 있다 (1000 ≤ A, B, C ≤ 15000). 그러나 외계인은 시간을 다르게 측정한다. 외계인의 1분은 N (2 ≤ N < 2 32) 외계인 초이다. 따라서 원판 가장자리에는 60개가 아니라 N개의 눈금이 있다.
시계의 유리 덮개가 깨지고 바늘이 헐거워졌다. 바늘은 서로 독립적으로 자유롭게 회전할 수 있다. 각 바늘을 임의의 눈금을 향하게 하면, 바늘 끝이 (일직선이 아닌 한) 가상의 삼각형을 이룰 수 있다.
도움이 올 때까지 기다리는 것 외에 할 일이 없는 외계인은 다음 질문을 고민한다. 시계의 중심을 포함하는 서로 다른 삼각형의 개수 M은 얼마인가? (중심이 삼각형의 변 위에 있는 삼각형도 포함한다.)
입력
입력은 한 줄에 A, B, C, N이 공백으로 구분되어 주어진다.
출력
M을 264로 나눈 나머지를 출력한다.