Пусть есть m пе­ре­мен­ных x₁, x₂, x₃, …, x_m-1, x_m и n пе­ре­мен­ных y₁, y₂, y₃, … y_n-1, y_n.

И пусть есть (m−1)*(n−1) урав­не­ний вида (x_i∧y_j→x_i+1∧y_j)∧(x_i∧y_j→x_i∧y_j+1)=1 для всех i<m и j<n. Конъ­юнк­ция двух вы­ра­же­ний равна 1 тогда и толь­ко тогда, когда каж­дое из двух вы­ра­же­ний равно 1. Сле­до­ва­тель­но, каж­дая из им­пли­ка­ций ис­тин­на.

Вос­поль­зу­ем­ся тем, что вы­ра­же­ние A→B рав­но­силь­но A≤B. Это зна­чит, что x_i∧y_j≤x_i+1∧y_j и x_i∧y_j≤x_i∧y_j+1 для всех i<m и j<n. Ис­хо­дя из этого, за­пи­шем зна­че­ния все­воз­мож­ных конъ­юнк­ций в таб­ли­цу, в ко­то­рой зна­че­ния в каж­дой стро­ке и каж­дом столб­це, кроме, воз­мож­но, по­след­них, не убы­ва­ют.

Рас­смот­рим ячей­ки таб­ли­цы со зна­че­ни­я­ми 1, рас­по­ло­жен­ные не в по­след­ней стро­ке и не в по­след­нем столб­це. Вы­бе­рем из них ячей­ки с ми­ни­маль­ным но­ме­ром стро­ки k, а среди них вы­бе­рем ячей­ку с ми­ни­маль­ным но­ме­ром столб­ца l. Это озна­ча­ет, что x_k∧y_l=1, а все конъ­юнк­ции x_i∧y_l=0, x_k∧y_j=0 и x_i∧y_j=0, где i<k и j<l. От­сю­да сле­ду­ет, что x_k=1 и y_l=1, а все x_i=0 и y_j=0, где i<k и j<l, по­это­му пер­вые (k−1) стро­ка и (l−1) стол­бец пол­но­стью со­сто­ят из нулей.

Внут­ри каж­дой стро­ки и каж­до­го столб­ца, кроме, воз­мож­но, по­след­них, зна­че­ния рас­по­ло­же­ны по прин­ци­пу не убы­ва­ния, по­это­му все клет­ки стро­ки k пра­вее вы­бран­ной ячей­ки, а также все клет­ки столб­ца l ниже вы­бран­ной ячей­ки, тоже долж­ны быть равны 1. По­это­му x_i=1 при k≤i≤m и y_j=1 при l≤j≤n, от­ку­да сле­ду­ет, что весь пра­вый ниж­ний пря­мо­уголь­ник со­сто­ит из еди­ниц.

По­лу­ча­ем, что для на­ше­го вы­бо­ра ячей­ки су­ще­ству­ет ровно одна таб­ли­ца зна­че­ний конъ­юнк­ций и ровно один набор пе­ре­мен­ных. По­сколь­ку ячей­ку со зна­че­ни­ем 1, на­хо­дя­щу­ю­ся не в по­след­нем столб­це и не в по­след­ней стро­ке, можно вы­брать (m−1)*(n−1) спо­со­ба­ми, сле­до­ва­тель­но, су­ще­ству­ет столь­ко же таб­лиц зна­че­ний конъ­юнк­ций и столь­ко же на­бо­ров пе­ре­мен­ных.

Те­перь рас­смот­рим слу­чай, когда такой ячей­ки нет, то есть на пе­ре­се­че­нии пер­вых (m−1) строк и пер­вых (n−1) столб­цов стоят толь­ко нули. Это озна­ча­ет, что x_i=0 при i<m или y_j=0 при j<n (воз­мож­но, од­но­вре­мен­но).

Если x_i=0 при i<m, то x_m и все y_j могут при­ни­мать любые зна­че­ния, то есть су­ще­ству­ет 2*2n ва­ри­ан­тов на­бо­ров пе­ре­мен­ных. Если y_j=0 при j<n, то y_n и все x_i могут при­ни­мать любые зна­че­ния, то есть су­ще­ству­ет 2*2m ва­ри­ан­тов.

Оста­лось по­счи­тать слу­чаи, ко­то­рые мы по­счи­та­ли два­жды. Если x_i=0 при i<m и y_j=0 при j<n, то эти на­бо­ры мы по­счи­та­ли 2 раза. В этих слу­ча­ях x_m и y_n могут быть лю­бы­ми, по­это­му имеем 4 лиш­них слу­чая.

В итоге по­лу­ча­ем фор­му­лу (m−1)*(n−1)+2ⁿ⁺¹+2^m+1−4.

Под­став­ляя зна­че­ния m  =  6 и n  =  7 по­лу­ча­ем:

Ответ: 410.