---

Problem 811

---

Bitwise Recursion

Let $b(n)$ be the largest power of $2$ that divides $n$. For example $b(24)=8$.

Define the recursive function:
$$\begin{array}{r}\begin{array}{rl}A(0)& =1\\ A(2n)& =3A(n)+5A(2n-b(n))n>0\\ A(2n+1)& =A(n)\end{array}\end{array}$$
and let $H(t,r)=A((2^t+1{)}^r)$.

You are given $H(3,2)=A(81)=636056$.

Find $H({10}^{14}+31,62)$. Give your answer modulo $1000062031$.

---

按位递归

记$b(n)$为最大的整除$n$的$2$的幂，例如$b(24)=8$。

定义如下递归关系式：
$$\begin{array}{r}\begin{array}{rl}A(0)& =1\\ A(2n)& =3A(n)+5A(2n-b(n))n>0\\ A(2n+1)& =A(n)\end{array}\end{array}$$
并记$H(t,r)=A((2^t+1{)}^r)$。

已知$H(3,2)=A(81)=636056$。

求$H({10}^{14}+31,62)$，并将你的答案对$1000062031$取余。

---