27519번 - 소수의 합

문제

소수 (Prime Number)란 1ドル$이 아니면서, 1ドル$과 자기 자신 이외에 약수가 존재하지 않는 양의 정수를 의미합니다. 예를 들어, 2ドル,ドル 3ドル,ドル 5ドル,ドル 7ドル$ 등이 소수에 해당합니다. 함수 $f(n)$을 "$n$을 0ドル$개 이상의 소수의 합으로 표현하는 경우의 수"로 정의합시다. 이 때, 소수의 종류는 중복해서 사용할 수 있으며, 종류가 같고 순서만 다른 경우는 같은 경우로 봅니다. 예를 들어, 5ドル$는 2ドル+3$ 또는 5ドル$로 나타낼 수 있으며, 다른 방법은 존재하지 않습니다. 따라서 $f(5)$는 2ドル$입니다.

정수 $n$이 주어질 때, $f(n)$의 값을 구하여 출력하세요. 단, 정답이 커질 수 있으니 정답을 1ドル ,円 000 ,円 000 ,円 007$로 나눈 나머지를 출력하세요.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$ (1ドル \le T \le 10,000円$)가 주어집니다.

두 번째 줄부터 $T+1$ 번째 줄까지 $i+1$ 번째 줄에 각각 정수 $n_i$ (0ドル < n_i \le 100,000円$)가 주어집니다.

출력

각 테스트 케이스에 대해 정답을 각각 한 줄에 출력하세요. 단, 정답이 커질 수 있으니 정답을 1ドル,000円,000円,007円$로 나눈 나머지를 출력하세요.

제한

힌트