골드바흐흑흙의 추측

시간 제한1초메모리 제한1024 MB

요약

구간 [A, B]에 속한 서로 다른 소수들의 부분집합 중 합이 K가 되는 경우의 수를 센다. 구간 길이는 최대 300, K는 2×10^9까지다.

문제

혁준이의 친한 친구 골드바흐흑흙은 호기심이 아주 많다.

어느 날, 골드바흐흑흙이 혁준이에게 물었다. 중복되지 않는 $A$ 이상 $B$ 이하인 소수들의 합으로 $K$ 를 표현할 수 있는 경우의 수는 얼마나 될까?

혁준이는 다섯 살이라서 골드바흐흑흙의 질문에 답할 수가 없으므로, 여러분이 대신 구해주자.

고른 수들은 같고 순서만 다른 경우들은 하나의 경우로 처리한다. 예를 들어, $\\{2,3\\}$ 과 $\\{3,2\\}$ 는 같은 경우이다.

첫 번째 줄에 양의 정수 $A, B, K$ 가 공백을 사이에 두고 주어진다. $(1 \le A < B \le 5 \times {10}^{7}; B - A \le 300;1 \le K \le 2 \times {10}^{9})$

문제의 정답을 출력한다.

답을 구하는 과정에서 정수 오버플로우가 발생할 수 있으며, 다음과 같은 정수 자료형 사용을 권장한다.