Дана сетка с \(n\) строками и \(m\) столбцами. Каждая ячейка сетки должна быть окрашена в синий или желтый цвет.
Раскраска сетки называется глупой, если в каждой строке есть ровно один отрезок синих ячеек, а в каждом столбце — ровно один отрезок желтых ячеек.
Другими словами, каждая строка должна иметь хотя бы одну синюю ячейку, и все синие ячейки в строке должны быть последовательными. Точно так же каждый столбец должен иметь хотя бы одну желтую ячейку, а все желтые ячейки в столбце должны быть последовательными.
Пример глупой раскраски.
Примеры умных раскрасок. В первой раскраске отсутствует синяя ячейка во втором ряду, а во второй раскраске есть два желтых отрезка во втором столбце. Сколько всего существует глупых раскрасок сетки? Две раскраски считаются различными, если есть какая-то ячейка, которая раскрашена в них в разные цвета.