32647번 - 골드바흐흑흙의 추측

문제

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

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

출력

문제의 정답을 출력한다.

제한

노트

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

• C, C++ : long long
• Java : long