Задача 537
Подсчет кортежей

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

Пусть T(n,k) будет количеством кортежей (x1,…,xk) длины k, для которых выполняется следующее:
1. Каждый xi - положительное целое число;
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(103,103) ≡ 578 270 566 (mod 1 004 535 809).

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

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net