시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 156 | 87 | 70 | 59.829% |
타고난 농사꾼 비니는 최근 숫자 공부에 푹 빠졌다. 열심히 숫자 공부를 하던 비니는 놀라 자빠질 수밖에 없었다. 숫자 7이 비니가 가장 아끼는 낫과 비슷하게 생겼기 때문이다. 옛말에 낫 놓고 7자도 모른다고 하였다. 문득 비니는 수를 구성하는 모든 숫자의 합과 곱이 7의 배수인 수가 몇 개인지 궁금해졌다. 비니는 답을 구하기 위하여 열심히 농사를 짓기로 결심하였다.
N이 주어졌을 때, N자리 양의 정수 중 수를 구성하는 모든 숫자의 합과 곱이 7의 배수인 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 없다.
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
이후 T개의 줄에 걸쳐 정수 N이 한 줄에 하나씩 주어진다.
각 테스트 케이스에 대한 답을 한 줄에 하나씩 출력한다. 답이 매우 커질 수 있으므로 109 + 7로 나눈 나머지를 출력한다.
4 1 2 3 4
1 2 54 692
2자리 수 중 조건을 만족하는 수는 70과 77이 있다.
4자리 수 중 조건을 만족하는 수는 2237 등이 있다. 2237의 경우 숫자들의 합은 2+2+3+7=14, 숫자들의 곱은 2×2×3×7=84이며, 14와 84는 모두 7의 배수이다.