# 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$$ を求めよ。
