Пусть $b(n)$ будет наибольшей степенью 2, которая делит $n$ нацело. Например, $b(24) = 8$.

Определим рекурсивную функцию: \begin{align*} \begin{split} A(0) &= 1\\ A(2n) &= 3A(n) + 5A\big(2n - b(n)\big) \qquad n \gt 0\\ A(2n+1) &= A(n) \end{split} \end{align*} Пусть $H(t,r) = A\big((2^t+1)^r\big)$.

Можно показать, что $H(3,2) = A(81) = 636056$.

Найдите $H(10^{14}+31,62)$. В качестве ответа приведите остаток от деления полученного результата на $1\,000\,062\,031$.