Европейская математическая олимпиада среди девочек (EGMO). 2022 год. Венгрия

Для каждой пары натуральных чисел $n$ и $k$ через $f(n, 2 k)$ обозначим количество способов, которыми можно полностью накрыть доску размера $n \times 2 k$ при помощи $n k$ доминошек размера $2 \times 1$. (Например, $f(2,2)=2$ и $f(3,2)=3$.)
   Найдите все натуральные числа $n$ такие, что для каждого натурального числа $k$ число $f(n, 2 k)$ нечётно.