Задача . D. Егор и пещеры

У Егора есть планшет. Экран планшета представляет собой прямоугольник n × m клеток, каждая из которых может быть либо черной, либо белой. Будем считать, что строки планшета пронумерованы целыми числами от 1 до n сверху вниз. Аналогично, столбцы планшета пронумерованы целыми числами от 1 до m слева направо.

Егор считает, что на экране планшета нарисована пещера, если выполнены следующие условия:

• Найдется отрезок [l, r] (1 ≤ l ≤ r ≤ n), такой, что в каждой из строк l, l + 1, ..., r, будет ровно две черные клетки, а во всех остальных строках все клетки будут белыми.
• Найдется строка с номером t (l ≤ t ≤ r), такая, что для всех пар строк с номерами i и j (l ≤ i ≤ j ≤ t) множество столбцов, содержащихся между черными клетками в строке номер i (вместе со столбцами, в которых находятся черные клетки), будет подмножеством множества столбцов, содержащихся между черными клетками в строке номер j (вместе со столбцами, в которых находятся черные клетки). Аналогично, для всех пар строк с номерами i и j (t ≤ i ≤ j ≤ r) множество столбцов, содержащихся между черными клетками в строке номер j (вместе со столбцами, в которых находятся черные клетки), будет подмножеством множества столбцов, содержащихся между черными клетками в строке номер i (вместе со столбцами, в которых находятся черные клетки).

Егора заинтересовал вопрос: сколько существует способов изобразить пещеру на его планшете. Два изображения считаются различными, если существует клетка, цвет которой отличается в этих изображениях.

Помогите Егору.