골드바흐흑흙의 추측

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

요약

A 이상 B 이하의 소수 중 서로 다른 소수를 골라 합이 K가 되는 방법의 수를 구합니다.

문제

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

어느 날, 골드바흐흑흙이 혁준이에게 물었다. 중복되지 않는 $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})$

문제의 정답을 출력한다.

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