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$로 나눈 나머지를 출력하세요.