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.
Təbii ədədlər və (2 \leq n \leq 5, 2 \leq m < 10^9).
Taxtanı gəzməyin üsullarının sayını 10^9 modulu ilə hesablayıb çıxarın.
Nümunə 1