Спот

Во пресрет на избори, се организира снимање на различни спотови за промоција на партиите. Една коалиција е составена од дури 21 партија и тие сакаат да направат спот кој ќе го снимат во огромна спортска сала, во која ќе бидат сместени членови од сите партии од коалицијата (некоја партија може да има повеќе членови-претставници во салата). Салата е изделена во правоаголна мрежа (матрица) од полиња во секое од кои може да стои најмногу еден претставник од некоја партија.

На пример, нека ги означиме претставниците од различните партии со следните ознаки: P01, P02, P03, …, P10, P11, …, P20, P21. Распоредот во салата може да изгледа вака (со ___ се означени празни позиции во салата каде што нема луѓе):

P01 P02 P03 P04 P05 P06 P07 P08 P09 P10 P14 P12 P13 P11 P15 P16 P17 ___ P19 ___ ___ ___ ___ ___ P17 ___ ___ ___ ___ P19 ___ ___ P10 ___ ___ P18 P21 P20


Ваша задача е да напишете програма која ќе пресмета колку различни спотови може да се направат, ако:

  • Спотот треба да се состои од движење (тура) на лидерот на коалицијата низ салата и поздравување со претставници од партиите
  • Лидерот мора да се поздрави со по точно еден претставник од секоја од партиите (ни помалку ни повеќе)
  • Лидерот може да се движи само во полиња во кои има претставник од некоја партија.
  • Лидерот може да започне и да заврши во кое било непразно поле
  • Лидерот се префрла од едно поле во друго, доколку полињата се соседни едно со друго. Со други зборови, дозволено е движење во некоја од следните четири насоки: горе, долу, лево, десно. (Забележете дека бидејќи има точно 21 партија, лидерот ќе се придвижи низ точно 21 поле во салата)
  • Два спота се различни доколку i-тото поле на кое се наоѓа лидерот во едниот спот е различно од i-тото поле во другиот спот, за кое било 1<=i<=21. Ако распоредот во салата го замислиме како матрица (како што е прикажано во примерот погоре), тогаш поле преставува вредност за ред и колона во соодветната матрица.



За распоред на салата како што е прикажан погоре, постојат 2 различни спота кои може да се снимат:

  • лидерот да тргне од позицијата горе-лево, да се движи десно се до 17-тото поле во првиот ред, и потоа да тргне надолу, па десно две полиња, па едно нагоре.
  • истиот пат како претходно, но изминат во обратна насока - т.е. лидерот да тргне од последното поле во првиот ред (каде е P19).



Влез

Во првиот ред се запишани два цели броја R и C (1 <= R, C <= 21), кои го означуваат бројот на редови и колони во правоаголната мрежа (матрицата). Во секој од следните R редови се запишани по C ознаки: P{XX} доколку во тоа поле се наоѓа претставник од одредена партија, или ___ доколку тоа е празно поле. Секоја од 21-те партии ќе има барем еден претставник во салата.

Во тест случаи кои вредат најмалку 20% од поените, ќе важи (R=2 или C=2).



Излез

Отпечатете го бараниот број на спотови.



Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes



Примери


влез
2 19
P01 P02 P03 P04 P05 P06 P07 P08 P09 P10 P14 P12 P13 P11 P15 P16 P17 ___ P19
___ ___ ___ ___ ___ P17 ___ ___ ___ ___ P19 ___ ___ P10 ___ ___ P18 P21 P20
излез
2


влез
15 5
___ ___ P01 ___ ___
___ ___ P02 ___ ___
___ ___ P03 ___ ___
___ ___ P04 ___ ___
___ ___ P05 ___ ___
___ ___ P06 ___ ___
___ ___ P07 ___ ___
___ ___ P08 ___ ___
___ ___ P09 ___ ___
___ ___ P10 ___ ___
P21 ___ P11 ___ P21
P20 ___ P12 ___ P20
P19 ___ P13 ___ P19
P18 ___ P14 ___ P18
P17 P16 P15 P16 P17


излез
4

 Submit your code