Дано множество {1,2,...,n}. Определим f(n,k) как количество его подмножеств в k элементов с нечетной суммой всех элементов. К примеру, f(5,3) = 4, так как множество {1,2,3,4,5} имеет четыре подмножества по три элемента, сумма чьих элементов нечетна: {1,2,4}, {1,3,5}, {2,3,4} и {2,4,5}.

Если все три значения n, k и f(n,k) нечетны, они образуют
нечетную тройку [n,k,f(n,k)].

Существует ровно пять нечетных троек для n ≤ 10, а именно:
[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¹² ?