주어진 순서대로 N개의 행렬을 곱한 뒤 결과 행렬의 모든 원소 합을 1,000,000,007로 나눈 나머지를 출력하고, 곱할 수 없으면 -1을 출력한다.
영우는 행렬을 공부하기 시작했지만 혼자서는 진도가 나가지 않아 효빈이에게 과외를 받기로 했다. 실력을 확인한 효빈이는 영우가 행렬 곱셈에 특히 약하다는 사실을 알고 행렬 곱셈을 숙제로 냈다. 숙제가 귀찮았던 영우는 곱셈을 대신 해 줄 프로그램을 당신에게 부탁했다.
행렬 NNN개가 주어진다. 주어진 순서대로 모두 곱한 뒤, 결과 행렬의 원소를 전부 더한 값을 구하는 프로그램을 작성하라.
입력은 표준 입력으로 받는다. 첫 줄에 행렬의 개수 NNN이 주어진다. (1≤N≤1001 \le N \le 1001≤N≤100)
이어서 NNN개의 행렬이 곱하는 순서대로 주어진다. 각 행렬은 첫 줄에 행의 개수 XXX와 열의 개수 YYY가 공백으로 구분되어 주어지고 (1≤X,Y≤501 \le X, Y \le 501≤X,Y≤50), 다음 XXX개의 줄에 한 행의 원소 YYY개가 공백으로 구분되어 주어진다. 원소는 모두 1 이상 100 이하의 정수다.
출력은 표준 출력으로 한다. 주어진 순서대로 행렬을 모두 곱한 결과 행렬의 원소를 전부 더하고, 그 값을 1,000,000,007로 나눈 나머지를 한 줄에 출력한다.
곱셈을 할 수 없으면 대신 -1을 출력한다. 어떤 행렬의 열 개수가 바로 뒤 행렬의 행 개수와 다른 곳이 한 군데라도 있으면 곱셈을 할 수 없다. NNN이 1이면 그 행렬의 원소 합을 출력한다.