집합 {1,2,...,n}에서, f(n,k)을 원소의 합이 홀수인 크기 k의 부분집합 개수라고 정의합니다. 예를 들어, f(5,3) = 4인데, 집합 {1,2,3,4,5}는 원소의 합이 홀수인 크기 3의 부분집합이 4개이기 때문입니다. 그들은 다음과 같습니다: {1,2,4}, {1,3,5}, {2,3,4}, {2,4,5}.

세 값 n, k, f(n,k)이 모두 홀수라면,
홀수 트리플 [n,k,f(n,k)]라고 부릅니다.

n ≤ 10일 때, 정확히 5개의 홀수 트리플이 있습니다. 그들은:
[1,1,f(1,1) = 1], [5,1,f(5,1) = 3], [5,5,f(5,5) = 1], [9,1,f(9,1) = 5], [9,9,f(9,9) = 1] 입니다.

n ≤ 10¹²일 때는 몇 개의 홀수 트리플이 있습니까 ?