Пусть x₁, x₂,..., x_n - последовательность длиной n, для которой справедливо:

• x₁ = 2
• x_i-1 < x_i при всех 1 < i < n
• (x_i) ^j < (x_j + 1)ⁱ для всех i и j при 1 ≤ i, j ≤ n

Существует всего пять таких последовательностей длиной 2, а именно: {2,4}, {2,5}, {2,6}, {2,7} и {2,8}.
Существует 293 такие последовательности длиной 5. Ниже представлены три примера:
{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⁹.