319 : 有界数列

$x_1, x_2, \dots, x_n$を以下のような長さ$n$の数列とする.

• $x_1 = 2$

• $1 < i \leq n$について$x_{i-1} < x_i$

• $1 \leq i,j \leq n$について$(x_i)^j < (x_j+1)^i$

長さ2のこのような数列は$\{2,4\}, \{2,5\}, \{2,6\}, \{2,7\}, \{2,8\}$の5つのみである. 長さ5のこのような数列は293ある. 以下がそのうちの3つの例である. $\{2,5,11,25,55\}, \{2,6,14,36,88\}, \{2,8,22,64,181\}$

$t(n)$を長さ$n$のこのような数列の個数とする. $t(10) = 86195, t(20) = 5227991891$である.

$t(10^{10})$を$\mod 10^9$で求めよ.