Областная олимпиада по математике 2018 года за 11 класс | Казахстанские олимпиады

Пусть ${{S}_{n}}=\left\{ 0,1,2,\ldots ,4n-1 \right\}.$ Подмножество $A$ множества ${{S}_{n}}$ называется редким, если для любого $k=0,1,2,\ldots ,n-1$ выполняются условия:
$\left| A\cap \left\{ 4k+1,4k+2,4k+3 \right\} \right|\le 1,$
$\left| A\cap \left\{ 4k-2,4k-1,4k,4k+1,4k+2 \right\} \right|\le 2.$
Найдите количество редких подмножеств. (Здесь $|M|$ означает количество элементов множества $M$.)