811 : ビット単位の再帰

$b(n)$ を、$n$ を割り切る最大の2の冪とする。例えば $b(24)=8$ である。

次のように再帰関数を定義する：

$A(0) = 1$ $A(2n) = 3A(n) + 5A(2n-b(n))$　$(n > 0)$ $A(2n+1) = A(n)$

また、$H(t,r) = A \big ((2^t+1)^r \big)$ とする。

$H(3,2) = A(81) = 636056$ が与えられている。

$H(10^{14} + 31, 62) \bmod 1\ 000\ 062\ 031$ を求めよ。