У Джан-Джи имеется кусок металла, из которого он хочет вырезать квадрат. Кусок состоит из сетки n на n, которую Джан-Джи может разрезать только по границам сетки. Каждая ячейка сетки либо исправная либо дефектная, при этом Джан-Джи хочет вырезать наибольший квадрат, не содержащий дефектных клеток. После определения максимального размера квадрата Джан-Джи хочет узнать сколькими различными способами он может вырезать его из имеющегося куска. После чего Джан-Джи следует вывести произведение максимального размера на количество способов расположения наибольшего квадрата.
Рассмотрим кусок материала размера 6 на 6. Черные ячейки дефектные. Наибольший квадрат, который может вырезать Джан-Джи, имеет размер 3 на 3, причем имеется два варианта его вырезать - красный и зеленый квадраты. Джан-Джи выведет произведение 3 и 2, то есть 6.
Вам следует найти размер наибольшего квадрата, который можно вырезать из куска материала, а также посчитать, сколькими различными вариантами это можно сделать. После чего вывести их произведение.
Первая строка содержит размер материала n (1 ≤ n ≤ 1000). Каждая из следующих n строк содержит n целых чисел. 1 означает что участок сетки целый, а 0 означает что участок сетки поврежден.
Вывести одно число – произведение размера наибольшего квадрата в материале на количество возможных его расположений в материале.