Problem 537

Counting tuples

Let π(x) be the prime counting function, i.e. the number of prime numbers less than or equal to x.
For example, π(1)=0, π(2)=1, π(100)=25.

Let T(n,k) be the number of k-tuples (x₁,…,x_k) which satisfy:

every x_i is a positive integer;
$\displaystyle \sum_{i=1}^k \pi(x_i)=n$

For example T(3,3)=19.
The 19 tuples are (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).

You are given T(10,10) = 869 985 and T(10³,10³) ≡ 578 270 566 (mod 1 004 535 809).

Find T(20 000, 20 000) mod 1 004 535 809.

元组计数

记π(x)为素数计数函数，即小于等于x的素数的数目。
例如，π(1)=0，π(2)=1，π(100)=25。

记T(n,k)为满足以下条件的k元组(x₁,…,x_k)的数目：

任意x_i都是正整数；
$\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。