Informatica Online Judge

  7의 배수 카드 게임 [0981 / 03D5]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 39   Total Tried : 328


The Champion of this Problem (C++) : gs17068 - 0ms / 736byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

수학을 좋아하는 경곽이는 유별나게 7의 배수를 좋아한다.

그 이유는 7의 배수를 판단하기 쉽지 않기 때문이다.

예를 들어 2의 배수는 맨 끝자리가 2의 배수이면 그 길이가 아무리 길더라도 2의 배수임을 알 수 있다.

3의 배수는 각 자리수의 합이 3의 배수이면 되며, 다른 배수들도 크게 어렵지 않게 배수를 판정할 수 있다.

하지만 7의 배수는 판정하는 방법이 제법 복잡한 편이다.

여기서 경곽이는 0 ~ 9로 이루어진 숫자카드를 가지고 재미있는 놀이를 생각했다.

숫자 카드 n^2개를 n행 n열로 뒤집어 배치하였다.

만약 n이 3일 때 다음과 같이 배치된다. ("#"은 카드의 뒷면)


# # #
# # #
# # #


게임의 규칙은 맨 왼쪽 위 카드를 먼저 뒤집는다.


1 # #
# # #
# # #


다음으로 방금 뒤집은 카드의 오른쪽 또는 아랫쪽 카드를 뒤집을 수 있다.

예를 들어 아랫쪽 카드를 뒤집었다고 하면,


1 # #
2 # #
# # #


과 같이 된다.

이와 같은 과정을 반복하여 가장 오른쪽 아래에 있는 카드를 뒤집으면 게임이 끝난다.


1 # #
2 3 #
# 4 1


뒤집은 순서대로 숫자를 결합하여 수를 만들어보면 "12341"이되며 이 수를 7로 나누면 나누어 떨어지므로 방금 만든 수 12341은 7의 배수임을 알 수 있다.

이와 같이 숫자 카드 2n-1장을 뒤집어 만든 수가 7의 배수이면 이 게임에서 이긴 것이다.

7의 배수가 아니라면 게임에서 진 것이다.

경곽이가 n*n개의 카드를 배치한 결과가 주어질 때, 이 게임에서 이길 수 있는 방법의 수를 모두 몇가지인가?

이를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 n의 값이 입력된다.
다음 줄 부터 n줄에 걸쳐서 n개의 값이 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= n <= 1,000
0 <= 각 카드의 값 <= 9
0은 모든 수의 배수로 취급한다.

[부분문제]
sub-task#1 : n <= 10 을 만족한다. (33.33%)
sub-task#2 : n <= 100 을 만족한다. (33.33%)
sub-task#3 : 입력값의 정의역과 같다. (33.33%)

Output

카드 게임을 이길 수 있는 모든 경우의 수를 출력한다. 단, 값이 너무 크기 때문에 모든 경우의 수를 1,000,000,007로 나눈 값을 출력한다.

IO Example

입력
3
7 1 7
7 1 7
7 2 7

출력
1

입력2
1
0

출력2
1

[해설] 0도 7로 나눈 나머지가 0이므로 7의 배수로 본다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]