Привет, Codeforces!

Недавно я столкнулся с интересной задачей на дп (может возможны другие подходы), но пока не могу ее решить.

Дана квадратная таблица размером n на n (n<=1000). Каждая ячейка таблицы либо черная, либо белая. Надо посчитать количество способов выбрать 2 непересекающихся черных прямоугольника. Под черным прямоугольником понимается любая подтаблица (в форме прямоугольника или квадрата) данной матрицы содержащая более 1 клетки и заполненная только черными клетками.

Буду очень благодарен за любую подсказку.

P.S Во всех тестах C — черная клетка, B — белая.