Oxatanın səyahəti#3442

Oxatanın səyahəti

1 saniyə
128 meqabayt
Çox asan

Oxçu, şahmat fiquru olaraq, bir xana irəli, geri, sola və sağa hərəkət edə bilir. O, n \times m ölçülü şahmat taxtasının xanada yerləşir (bu taxtanın sağ üst xanası nömrəlidir). Oxçunun məqsədi bütün taxtanı gəzmək və başlanğıc xanaya qayıtmaqdır. Bu səyahət zamanı o, taxtanın hər bir xanasında dəqiq bir dəfə olmalıdır (səyahət oxçunun ilk hərəkətindən başlayır). Biz oxçunun taxtanı neçə fərqli üsulla gəzə biləcəyini öyrənmək istəyirik.

Giriş

Təbii ədədlər və (2 \leq n \leq 5, 2 \leq m < 10^9).

Çıxış

Taxtanı gəzməyin üsullarının sayını 10^9 modulu ilə hesablayıb çıxarın.

Nümunələr

Nümunə 1

Loading
Loading