Problem 319

Bounded Sequences

Let x₁, x₂,…, x_n be a sequence of length n such that:

x₁ = 2
for all 1 < i ≤ n : x_i-1 < x_i
for all i and j with 1 ≤ i, j ≤ n : (x_i)^j < (x_j + 1)ⁱ

There are only five such sequences of length 2, namely: {2,4}, {2,5}, {2,6}, {2,7} and {2,8}.
There are 293 such sequences of length 5; three examples are given below:
{2,5,11,25,55}, {2,6,14,36,88}, {2,8,22,64,181}.

Let t(n) denote the number of such sequences of length n.
You are given that t(10) = 86195 and t(20) = 5227991891.

Find t(10¹⁰) and give your answer modulo 10⁹.

有界序列

记x₁, x₂,…, x_n是长度为n的序列，且满足：

x₁ = 2
对于所有1 < i ≤ n：x_i-1 < x_i
对于所有1 ≤ i, j ≤ n：(x_i)^j < (x_j + 1)ⁱ

在长度为2的序列中，这样的数列只有5个，分别是：{2,4}、{2,5}、{2,6}、{2,7}和{2,8}。
在长度为5的序列中，这样的数列共有293个；如下是其中三个例子：
{2,5,11,25,55}、{2,6,14,36,88}、{2,8,22,64,181}。

在长度为n的序列中，记这样的数列有t(n)个。
已知t(10) = 86195以及t(20) = 5227991891。

求t(10¹⁰)并将你的答案模10⁹取余。