Пусть π(x) будет функцией подсчета простых чисел, т.е. количеством простых чисел меньше или равных x.
Например, π(1)=0, π(2)=1, π(100)=25.

Пусть T(n,k) будет количеством кортежей (x₁,…,x_k) длины k, для которых выполняется следующее:
1. Каждый x_i - натуральное число;
2. $\displaystyle \sum_{i=1}^k \pi(x_i)=n$

Например, T(3,3)=19.
Вот эти 19 кортежей: (1,1,5), (1,5,1), (5,1,1), (1,1,6), (1,6,1), (6,1,1), (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1), (1,2,4), (1,4,2), (2,1,4), (2,4,1), (4,1,2), (4,2,1), (2,2,2).

Известно, что T(10,10) = 869 985 и T(10³,10³) ≡ 578 270 566 (mod 1 004 535 809).

Найдите T(20 000, 20 000) mod 1 004 535 809.