20957번 - 농부 비니

문제

타고난 농사꾼 비니는 최근 숫자 공부에 푹 빠졌다. 열심히 숫자 공부를 하던 비니는 놀라 자빠질 수밖에 없었다. 숫자 7이 비니가 가장 아끼는 낫과 비슷하게 생겼기 때문이다. 옛말에 낫 놓고 7자도 모른다고 하였다. 문득 비니는 수를 구성하는 모든 숫자의 합과 곱이 7의 배수인 수가 몇 개인지 궁금해졌다. 비니는 답을 구하기 위하여 열심히 농사를 짓기로 결심하였다.

N이 주어졌을 때, N자리 양의 정수 중 수를 구성하는 모든 숫자의 합과 곱이 7의 배수인 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 없다.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

이후 T개의 줄에 걸쳐 정수 N이 한 줄에 하나씩 주어진다.

출력

각 테스트 케이스에 대한 답을 한 줄에 하나씩 출력한다. 답이 매우 커질 수 있으므로 10⁹ + 7로 나눈 나머지를 출력한다.

제한

• 1 ≤ T ≤ 10,000
• 1 ≤ N ≤ 10,000

힌트

2자리 수 중 조건을 만족하는 수는 70과 77이 있다.

4자리 수 중 조건을 만족하는 수는 2237 등이 있다. 2237의 경우 숫자들의 합은 2+2+3+7=14, 숫자들의 곱은 2×2×3×7=84이며, 14와 84는 모두 7의 배수이다.