Определим $Q(n)$ как наименьшее число, встречающееся в ровно $n$ пифагоровых тройках $(a,b,c)$, где $a \lt b \lt c$.

Например, 15 - наименьшее число, встречающееся ровно в 5 пифагоровых тройках: $$(9,12,\mathbf{15})\quad (8,\mathbf{15},17)\quad (\mathbf{15},20,25)\quad (\mathbf{15},36,39)\quad (\mathbf{15},112,113)$$, поэтому $Q(5) = 15$

Также известно, что $Q(10)=48$ и $Q(10^3)=8064000$.

Найдите $\displaystyle \sum_{k=1}^{18} Q(10^k)$. В качестве ответа приведите остаток от деления полученного результата на $409120391$.