Фиолетовые матрицы

Слабомонотонной будем называть последовательность, которая либо не возрастает, либо не убывает. Например, 000, 111, 100 — слабомонотонные последовательности, а 101 или 010 — уже нет. Матрица называется фиолетовой, если каждая её строка и каждый её столбец представляют собой слабомонотонную последовательность. Рассмотрим двоичные матрицы, то есть такие, у которых элементы — 0 или 1.

Сколько бывает двоичных фиолетовых матриц M×N (нужно выразить через M и N)?