Коэффициенты разложения $(x+1)^k$ называются биномиальными коэффициентами.
Аналогичным образом, коэффициенты разложения $(x^4+x^3+x^2+x+1)^k$ называются квинтиномиальными коэффициентами.
(Quintus на латыни - "пятый").

Рассмотрим разложение $(x^4+x^3+x^2+x+1)^3$:
$x^{12}+3x^{11}+6x^{10}+10x^9+15x^8+18x^7+19x^6+18x^5+15x^4+10x^3+6x^2+3x+1$
Как видно, 7 из 13 квинтиномиальных коэффициентов для $k=3$ являются нечетными.

Пусть $Q(k)$ будет количеством нечетных коэффициентов разложения $(x^4+x^3+x^2+x+1)^k$.
Таким образом, $Q(3)=7$.

Известно, что $Q(10)=17$ и $Q(100)=35$.

Найдите $\sum_{k=1}^{18}Q(10^k) $.