생명 게임

당신은 생물 무기를 생산하는 공장에서 일한다. 당신이 맡은 것은 번식력이 매우 강한 끔찍한 바이러스 무기를 관리하는 일이다. 이 바이러스는 정육각형 모양의 군집을 규칙적으로 만드는 경향이 있어서, 무기 전체가 육각형 격자를 이루고 육각형 하나가 군집 하나에 해당한다. 격자는 각 변에 $N$개의 군집이 있는 정육각형 모양이다. 바이러스는 일정한 속도로 자기 증식하며, 증식은 모든 군집에서 동시에 일어난다. 증식이 끝나면 각 군집은 이웃한 모든 군집에 같은 수의 바이러스를 새로 낳는다. 증식 후 한 군집의 바이러스 수가 한계 밀도 $M$ 이상이면, 그 군집의 바이러스는 자기 공격을 시작하고 바이러스 수는 $M$으로 나눈 나머지로 줄어든다. 격자의 크기 $N$과 각 군집의 초기 바이러스 수가 주어질 때, $L$번의 주기가 지난 뒤 모든 군집의 바이러스 총수를 구하는 것이 과제다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스는 세 정수 $N$ ($1 \le N \le 6$), $M$ ($2 \le M \le 10^9$), $L$ ($1 \le L \le 10^9$)이 적힌 줄로 시작한다. 이어지는 $2N-1$개의 줄이 초기 상태를 나타낸다. 각 음이 아닌 정수는 $M$보다 작으며, 해당 군집의 초기 바이러스 수이다. 첫 줄에는 맨 윗줄 $N$개 군집의 바이러스 수를 왼쪽에서 오른쪽 순서로 주고, 둘째 줄에는 그다음 줄 $N+1$개 군집의 값을 준다. 이런 방식으로 아래 줄까지 이어진다. 입력의 끝은 0 0 0이 적힌 줄로 표시된다.

각 테스트 케이스마다 테스트 케이스 번호를 출력한 뒤, $L$번의 주기가 지난 후 모든 군집의 바이러스 총수를 출력한다.