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

문제

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

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+XHJcblx0QVx1Yjk3YyBwICZ0aW1lczsgcSBcdWQ1ODlcdWI4MmMsIEJcdWI5N2MgbiAmdGltZXM7IG0gXHVkNTg5XHViODJjXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0IFx1YjU0YywgQVx1YzY0MCBCXHViMjk0IDEgJnRpbWVzOyAxIFx1ZDU4OVx1YjgyY1x1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdEFcdWM2NDAgQlx1Yzc1OCBcdWQxNTBcdWMxMWMgXHVhY2YxIEEgJm90aW1lczsgQlx1YjI5NCBwbiAmdGltZXM7IHFtIFx1ZDU4OVx1YjgyY1x1Yzc3NCBcdWI0MThcdWFjZTAsIEFcdWM3NTggXHViYWE4XHViNGUwIFx1YzZkMFx1YzE4YyBhPHN1Yj5pajxcL3N1Yj5cdWI5N2MgXHVkNTg5XHViODJjIChhPHN1Yj5pajxcL3N1Yj4pICZtaWRkb3Q7IEJcdWI4NWMgXHViYzE0XHVhZmJjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM1NDRcdWI3OThcdWIyOTQgXHVkNTg5XHViODJjXHVjNzU4IFx1ZDE1MFx1YzExYyBcdWFjZjFcdWM3NTggXHVjNjA4XHVjMmRjXHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RlbnNvci5wbmdcIiBzdHlsZT1cIndpZHRoOiA2NjFweDsgaGVpZ2h0OiAxMjJweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzdjXHViYzE4XHVjODAxXHVjNzc4IFx1ZDU4OVx1YjgyYyBcdWFjZjFcdWFjZmNcdWIyOTQgXHViMmU0XHViOTc0XHVhYzhjLCBxXHVjNjQwIG5cdWM3NzQgXHVhYzE5XHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWM4NzBcdWFjNzRcdWM3NzQgXHVjNWM2XHViMmU0LiBcdWM1YjRcdWI1YTQgXHVkNTg5XHViODJjXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDE1MFx1YzExYyBcdWFjZjFcdWM3M2NcdWI4NWMgXHVjNzc0IFx1ZDU4OVx1YjgyY1x1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVhYzAwXHVjOWQzXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWQwNmNcdWFlMzAgclx1YWNmYyBjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIHJcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWFjMDEgXHVjNmQwXHVjMThjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gclx1YWNmYyBjXHViMjk0IDUwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LiBcdWI2MTAsIFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWFjMDEgXHVjNmQwXHVjMThjXHViMjk0IDY1NTM2XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWQxNTBcdWMxMWMgXHVhY2YxXHVjNzNjXHViODVjJm5ic3A7XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWQ1ODlcdWI4MmNcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViNDUwIFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQwNDkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIZXJlXHUyMDE5cyBhIFByb2R1Y3QgV2hpY2ggV2lsbCBNYWtlIFlvdSBUZW5zb3IiLCJkZXNjcmlwdGlvbiI6IjxwPk1vc3QgcGVvcGxlIGFyZSBmYW1pbGlhciB3aXRoIGhvdyB0byBtdWx0aXBseSB0d28gbWF0cmljZXMgdG9nZXRoZXIuIEhvd2V2ZXIsIGFuIGFsdGVybmF0ZSBmb3JtIG9mIG11bHRpcGxpY2F0aW9uIGtub3duIGFzIHRlbnNvciBtdWx0aXBsaWNhdGlvbiBleGlzdHMgYXMgd2VsbCwgYW5kIHdvcmtzIG1vcmUgbGlrZSB5b3Ugd291bGQgZXhwZWN0IG1hdHJpeCBtdWx0aXBsaWNhdGlvbiBzaG91bGQuIExldCBBIGJlIGEgcCAmdGltZXM7IHEgbWF0cml4IGFuZCBCIGJlIGFuIG4gJnRpbWVzOyBtIG1hdHJpeCwgd2hlcmUgbmVpdGhlciBBIG5vciBCIGlzIGEgMSAmdGltZXM7IDEgbWF0cml4LiBUaGVuIHRoZSB0ZW5zb3IgcHJvZHVjdCBBICZvdGltZXM7IEIgaXMgYSBwbiAmdGltZXM7IHFtIG1hdHJpeCBmb3JtZWQgYnkgcmVwbGFjaW5nIGVhY2ggZWxlbWVudCBhPHN1Yj5pajxcL3N1Yj4gaW4gQSB3aXRoIHRoZSBtYXRyaXggKGE8c3ViPmlqPFwvc3ViPikgJm1pZGRvdDsgQi4gVHdvIGV4YW1wbGVzIGFyZSBzaG93biBiZWxvdywgd2hpY2ggYWxzbyBkZW1vbnN0cmF0ZSB0aGF0LCBsaWtlIG5vcm1hbCBtYXRyaXggbXVsdGlwbGljYXRpb24sIHRlbnNvciBtdWx0aXBsaWNhdGlvbiBpcyBub24tY29tbXV0YXRpdmU6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdGVuc29yLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyMnB4OyB3aWR0aDo2NjFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgdGhlcmUgaXMgbm8gcmVzdHJpY3Rpb24gdGhhdCB0aGUgbnVtYmVyIG9mIGNvbHVtbnMgaW4gdGhlIGZpcnN0IG1hdHJpeCBtdXN0IGVxdWFsIHRoZSBudW1iZXIgb2Ygcm93cyBpbiB0aGUgc2Vjb25kLCBhcyB0aGVyZSBpcyB3aXRoIG5vcm1hbCBtYXRyaXggbXVsdGlwbGljYXRpb24uIFRoZSBvYmplY3Qgb2YgdGhpcyBwcm9ibGVtIGlzIHRvIGRldGVybWluZSB0aGUgbnVtYmVyIG9mIHdheXMgKGlmIGFueSkgYSBnaXZlbiBtYXRyaXggY2FuIGJlIGZvcm1lZCBhcyBhIHJlc3VsdCBvZiBhIHRlbnNvciBtdWx0aXBsaWNhdGlvbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGZvciBhIHRlc3QgY2FzZSB3aWxsIGNvbnRhaW4gdHdvIHBvc2l0aXZlIGludGVnZXJzIHIgYW5kIGMgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHJvd3MgYW5kIGNvbHVtbnMgaW4gdGhlIG1hdHJpeC4gQWZ0ZXIgdGhpcyB3aWxsIGZvbGxvdyByIGxpbmVzIGVhY2ggY29udGFpbmluZyBjIHBvc2l0aXZlIGludGVnZXJzLiBUaGUgdmFsdWVzIG9mIHIgYW5kIGMgd2lsbCBiZSAmbGU7IDUwMCwgZWFjaCBlbnRyeSBpbiB0aGUgbWF0cml4IHdpbGwgYmUgbm8gZ3JlYXRlciB0aGFuIDY1LDUzNiwgYW5kIHRoZSBsYXN0IHRlc3QgY2FzZSBpcyBmb2xsb3dlZCBieSBhIGxpbmUgY29udGFpbmluZyAwIDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgd2F5cyB0aGUgbWF0cml4IGNvdWxkIGJlIHRoZSB0ZW5zb3IgcHJvZHVjdCBvZiB0d28gcG9zaXRpdmUgaW50ZWdlciBtYXRyaWNlcywgbmVpdGhlciBvZiB3aGljaCBpcyBhIDEgJnRpbWVzOyAxIG1hdHJpeC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=