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

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

Существует всего пять таких последовательностей длинной 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⁹.