시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 13 3 2 25.000%

문제

두 행렬을 곱하는 또다른 방법이 있다. 이 방법은 텐서 곱이라고 한다.

A를 p × q 행렬, B를 n × m 행렬이라고 하자. 이때, A와 B는 1 × 1 행렬이 아니다.

A와 B의 텐서 곱 A ⊗ B는 pn × qm 행렬이 되고, A의 모든 원소 aij를 행렬 (aij) · B로 바꾼다.

아래는 행렬의 텐서 곱의 예시이다. 

일반적인 행렬 곱과는 다르게, q와 n이 같아야 한다는 조건이 없다. 어떤 행렬이 주어졌을 때, 텐서 곱으로 이 행렬을 만들 수 있는 행렬의 가짓수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 행렬의 크기 r과 c가 주어진다. 다음 r개의 줄에는 행렬의 각 원소가 주어진다. r과 c는 500보다 작거나 같다. 또, 행렬의 각 원소는 65536보다 작거나 같다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 텐서 곱으로 입력으로 주어진 행렬을 만들 수 있는 두 행렬의 서로 다른 방법의 수를 출력한다.

예제 입력 1

6 6
1 1 1 2 2 2
1 1 1 2 2 2
1 1 2 2 2 4
3 3 3 4 4 4
3 3 3 4 4 4
3 3 6 4 4 8
2 2
3 6
4 9
2 4
15 18 30 36
20 24 40 48
0 0

예제 출력 1

1
0
4
W3sicHJvYmxlbV9pZCI6IjQwNDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1ODlcdWI4MmNcdWM3NTggXHVkMTUwXHVjMTFjXHVhY2YxIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWI0NTAgXHVkNTg5XHViODJjXHVjNzQ0IFx1YWNmMVx1ZDU1OFx1YjI5NCBcdWI2MTBcdWIyZTRcdWI5NzggXHViYzI5XHViYzk1XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWQxNTBcdWMxMWMgXHVhY2YxXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0QVx1Yjk3YyBwICZ0aW1lczsgcSBcdWQ1ODlcdWI4MmMsIEJcdWI5N2MgbiAmdGltZXM7IG0gXHVkNTg5XHViODJjXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViNTRjLCBBXHVjNjQwIEJcdWIyOTQgMSAmdGltZXM7IDEgXHVkNTg5XHViODJjXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0QVx1YzY0MCBCXHVjNzU4IFx1ZDE1MFx1YzExYyBcdWFjZjEgQSAmb3RpbWVzOyBCXHViMjk0IHBuICZ0aW1lczsgcW0gXHVkNTg5XHViODJjXHVjNzc0IFx1YjQxOFx1YWNlMCwgQVx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNmQwXHVjMThjIGE8c3ViPmlqPFwvc3ViPlx1Yjk3YyBcdWQ1ODlcdWI4MmMgKGE8c3ViPmlqPFwvc3ViPikgJm1pZGRvdDsgQlx1Yjg1YyBcdWJjMTRcdWFmYmNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzU0NFx1Yjc5OFx1YjI5NCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVkMTUwXHVjMTFjIFx1YWNmMVx1Yzc1OCBcdWM2MDhcdWMyZGNcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdGVuc29yLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDY2MXB4OyBoZWlnaHQ6IDEyMnB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3N2NcdWJjMThcdWM4MDFcdWM3NzggXHVkNTg5XHViODJjIFx1YWNmMVx1YWNmY1x1YjI5NCBcdWIyZTRcdWI5NzRcdWFjOGMsIHFcdWM2NDAgblx1Yzc3NCBcdWFjMTlcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0XHViMjk0IFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWM1YzZcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWQ1ODlcdWI4MmNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMTUwXHVjMTFjIFx1YWNmMVx1YzczY1x1Yjg1YyBcdWM3NzQgXHVkNTg5XHViODJjXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWFjMDBcdWM5ZDNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTg5XHViODJjXHVjNzU4IFx1ZDA2Y1x1YWUzMCByXHVhY2ZjIGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgclx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTg5XHViODJjXHVjNzU4IFx1YWMwMSBcdWM2ZDBcdWMxOGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiByXHVhY2ZjIGNcdWIyOTQgNTAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuIFx1YjYxMCwgXHVkNTg5XHViODJjXHVjNzU4IFx1YWMwMSBcdWM2ZDBcdWMxOGNcdWIyOTQgNjU1MzZcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWI0NTAgXHVhYzFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1ZDE1MFx1YzExYyBcdWFjZjFcdWM3M2NcdWI4NWMmbmJzcDtcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDU4OVx1YjgyY1x1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHVkNTg5XHViODJjXHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDA0OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhlcmVcdTIwMTlzIGEgUHJvZHVjdCBXaGljaCBXaWxsIE1ha2UgWW91IFRlbnNvciIsImRlc2NyaXB0aW9uIjoiPHA+TW9zdCBwZW9wbGUgYXJlIGZhbWlsaWFyIHdpdGggaG93IHRvIG11bHRpcGx5IHR3byBtYXRyaWNlcyB0b2dldGhlci4gSG93ZXZlciwgYW4gYWx0ZXJuYXRlIGZvcm0gb2YgbXVsdGlwbGljYXRpb24ga25vd24gYXMgdGVuc29yIG11bHRpcGxpY2F0aW9uIGV4aXN0cyBhcyB3ZWxsLCBhbmQgd29ya3MgbW9yZSBsaWtlIHlvdSB3b3VsZCBleHBlY3QgbWF0cml4IG11bHRpcGxpY2F0aW9uIHNob3VsZC4gTGV0IEEgYmUgYSBwICZ0aW1lczsgcSBtYXRyaXggYW5kIEIgYmUgYW4gbiAmdGltZXM7IG0gbWF0cml4LCB3aGVyZSBuZWl0aGVyIEEgbm9yIEIgaXMgYSAxICZ0aW1lczsgMSBtYXRyaXguIFRoZW4gdGhlIHRlbnNvciBwcm9kdWN0IEEgJm90aW1lczsgQiBpcyBhIHBuICZ0aW1lczsgcW0gbWF0cml4IGZvcm1lZCBieSByZXBsYWNpbmcgZWFjaCBlbGVtZW50IGE8c3ViPmlqPFwvc3ViPiBpbiBBIHdpdGggdGhlIG1hdHJpeCAoYTxzdWI+aWo8XC9zdWI+KSAmbWlkZG90OyBCLiBUd28gZXhhbXBsZXMgYXJlIHNob3duIGJlbG93LCB3aGljaCBhbHNvIGRlbW9uc3RyYXRlIHRoYXQsIGxpa2Ugbm9ybWFsIG1hdHJpeCBtdWx0aXBsaWNhdGlvbiwgdGVuc29yIG11bHRpcGxpY2F0aW9uIGlzIG5vbi1jb21tdXRhdGl2ZTo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90ZW5zb3IucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTIycHg7IHdpZHRoOjY2MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk5vdGUgdGhhdCB0aGVyZSBpcyBubyByZXN0cmljdGlvbiB0aGF0IHRoZSBudW1iZXIgb2YgY29sdW1ucyBpbiB0aGUgZmlyc3QgbWF0cml4IG11c3QgZXF1YWwgdGhlIG51bWJlciBvZiByb3dzIGluIHRoZSBzZWNvbmQsIGFzIHRoZXJlIGlzIHdpdGggbm9ybWFsIG1hdHJpeCBtdWx0aXBsaWNhdGlvbi4gVGhlIG9iamVjdCBvZiB0aGlzIHByb2JsZW0gaXMgdG8gZGV0ZXJtaW5lIHRoZSBudW1iZXIgb2Ygd2F5cyAoaWYgYW55KSBhIGdpdmVuIG1hdHJpeCBjYW4gYmUgZm9ybWVkIGFzIGEgcmVzdWx0IG9mIGEgdGVuc29yIG11bHRpcGxpY2F0aW9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgZm9yIGEgdGVzdCBjYXNlIHdpbGwgY29udGFpbiB0d28gcG9zaXRpdmUgaW50ZWdlcnMgciBhbmQgYyBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2Ygcm93cyBhbmQgY29sdW1ucyBpbiB0aGUgbWF0cml4LiBBZnRlciB0aGlzIHdpbGwgZm9sbG93IHIgbGluZXMgZWFjaCBjb250YWluaW5nIGMgcG9zaXRpdmUgaW50ZWdlcnMuIFRoZSB2YWx1ZXMgb2YgciBhbmQgYyB3aWxsIGJlICZsZTsgNTAwLCBlYWNoIGVudHJ5IGluIHRoZSBtYXRyaXggd2lsbCBiZSBubyBncmVhdGVyIHRoYW4gNjUsNTM2LCBhbmQgdGhlIGxhc3QgdGVzdCBjYXNlIGlzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIDAgMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCB3YXlzIHRoZSBtYXRyaXggY291bGQgYmUgdGhlIHRlbnNvciBwcm9kdWN0IG9mIHR3byBwb3NpdGl2ZSBpbnRlZ2VyIG1hdHJpY2VzLCBuZWl0aGVyIG9mIHdoaWNoIGlzIGEgMSAmdGltZXM7IDEgbWF0cml4LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==