x₁, x₂,..., x_n은 다음을 만족하는 길이 n의 수열입니다:

• x₁ = 2
• 모든 1 < i ≤ n에서 : x_i-1 < x_i
• 1 ≤ i, j ≤ n인 모든 i, j에서 : (x_i) ^j < (x_j + 1)ⁱ

길이 2인 그런 수열은 모두 5개고, 다음과 같습니다: {2,4}, {2,5}, {2,6}, {2,7}, {2,8}.
길이 5인 그런 수열은 모두 293개고, 그 중 3개만 예를 들면 다음과 같습니다:
{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⁹로 나눈 나머지를 답으로 제출하세요.