令 $x_1,x_2,\dots ,x_n$ 为长度为 $n$ 的序列，使得：

• $x_1=2$
• 对于所有 $1<i\le n$：$x_{i-1}<x_i$
• 对于所有 $i$ 和 $j$，其中 $1\le i,j\le n$：$(x_i{)}^j<(x_j+1{)}^i$。

这样的长度为$2$的序列只有五个，即： $\{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\}$。

让 $t(n)$ 表示长度为 $n$ 的此类序列的数量。
已知 $t(10)=86195$ 和 $t(20)=5227991891$。

求 $t({10}^{10})$ 并以 ${10}^9$ 为模给出你的答案。