시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 145 36 32 34.043%

문제

영우는 최근 행렬에 대해 관심을 갖기 시작했다. 하지만 혼자 공부하기 힘들었던 영우는 효빈이에게 과외를 받기로 했다. 영우의 실력을 테스트 해본 효빈이는 영우가 행렬의 곱셈을 너무나도 못한다는 사실을 깨닫고, 영우의 실력 증진을 위해 단순 행렬 곱셈 문제를 숙제로 내주었다. 하지만 너무나 귀찮은 영우는 당신에게 행렬의 곱셈을 대신 해주는 프로그램을 부탁했다. 효빈이에게는 미안하지만 영우를 위해 행렬의 곱셈을 해주는 프로그램을 만들어주자.

입력

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 행렬의 총 개수N이 주어진다. (1 ≤ N ≤ 100) 다음줄부터 N개의 행렬이 차례대로 주어진다. 각 행렬의 입력 첫 줄에는 X와 Y가 주어진다. X는 행의 개수이고 Y는 열의 개수이다. (1 ≤ X, Y ≤ 50) 다음 X줄에 걸쳐서 Y개의 행렬 원소가 주어진다. 각 원소의 값은 1이상 100이하 이다.

출력

프로그램의 출력은 표준 출력으로 한다. 최종으로 나온 행렬의 원소들의 합을 1,000,000,007로 나눈 나머지를 출력한다. 만약 행렬의 곱셈을 할 수 없다면 -1을 출력한다.

예제 입력

2
1 2
1 1
2 2
5 6
7 8

예제 출력

26

예제 입력 2

2
1 2
1 2
1 4
3 2 4 6

예제 출력 2

-1

힌트