효빈이의 과외

주어진 순서대로 N개의 행렬을 곱한 뒤 결과 행렬의 모든 원소 합을 1,000,000,007로 나눈 나머지를 출력하고, 곱할 수 없으면 -1을 출력한다.

쉬움3구현수학배열면접 대비아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

영우는 행렬을 공부하기 시작했지만 혼자서는 진도가 나가지 않아 효빈이에게 과외를 받기로 했다. 실력을 확인한 효빈이는 영우가 행렬 곱셈에 특히 약하다는 사실을 알고 행렬 곱셈을 숙제로 냈다. 숙제가 귀찮았던 영우는 곱셈을 대신 해 줄 프로그램을 당신에게 부탁했다.

행렬 NN개가 주어진다. 주어진 순서대로 모두 곱한 뒤, 결과 행렬의 원소를 전부 더한 값을 구하는 프로그램을 작성하라.

입력

입력은 표준 입력으로 받는다. 첫 줄에 행렬의 개수 NN이 주어진다. (1N1001 \le N \le 100)

이어서 NN개의 행렬이 곱하는 순서대로 주어진다. 각 행렬은 첫 줄에 행의 개수 XX와 열의 개수 YY가 공백으로 구분되어 주어지고 (1X,Y501 \le X, Y \le 50), 다음 XX개의 줄에 한 행의 원소 YY개가 공백으로 구분되어 주어진다. 원소는 모두 1 이상 100 이하의 정수다.

출력

출력은 표준 출력으로 한다. 주어진 순서대로 행렬을 모두 곱한 결과 행렬의 원소를 전부 더하고, 그 값을 1,000,000,007로 나눈 나머지를 한 줄에 출력한다.

곱셈을 할 수 없으면 대신 -1을 출력한다. 어떤 행렬의 열 개수가 바로 뒤 행렬의 행 개수와 다른 곳이 한 군데라도 있으면 곱셈을 할 수 없다. NN이 1이면 그 행렬의 원소 합을 출력한다.