Pişiyi xilas etməli
Pişiyi xilas etməli
Artur xallar toplamaq üçün müxtəlif intellektual və fiziki məsələlərin həll edilməsi tələb olunan teleşouda iştirak edir. Belə tapşırıqların birində Artur pişiyi xilas etməlidir.
Məsələni həll etmək üçün sahə vahid sahəli kvadratlara ayrılmış n×m metr ölçülü düzbucaqlıdır. Kvadratların birində Artur cari mövqeyindədir, başqa bir kvadratda isə pişik var. Bundan başqa kvadratlardan birində lift yerləşir. Arturun məsələni müvəffəqiyyətlə həll edir.
Bir addımda Artur onun durduğu kvadratla qonşu olan (ümumi tərəfi olan) istənilən kvadrata keçə bilər. Bundan sonra bu addımdan əvvəl Arturun olduğu kvadrat yox olur və artıq onun üzərində durmaq olmaz. Beləliklə, Arturun durduğu və pişiyin olduğu cari kvadratlar yox olurlar. Arturun məqsədi — pişiyin olduğu yerə çatmaq, onu götürmək və sonra liftə çatmaqdır. Bu zaman məsələnin həlli üçün verilən xal Arturun atdığı addımların sayından asılıdır, buna görə minimal sayda addım atmaq lazımdır.
Neçə addım atmalı olduğunu təyin edərək, Artur maraqlandı ki, pişiyə çatmaq, sonra da onunla liftə çatmaq üçün neçə müxtəlif üsul var və bu zaman minimal sayda addımlar atmaq lazımdır. Bunu müəyyənləşdirmək üçün ona kömək edin. Bu ədəd kifayət qədər böyük ola bilər, buna görə də Artur bunu 10^9+7 modluna görə tapmağı xahiş edir.
Giriş verilənləri
Giriş faylının ilk sətri məsələnin həlli üçün sahənin ölçülərini ifadə edən n və m (2 ≤ n, m ≤ 100) natural ədədləri ehtiva edir.
İkinci sətirdə Arturun olduğu cari kvadratın koordinatlarını ifadə edən iki x_A və y_A (1 ≤ x_A ≤ n, 1 ≤ y_A ≤ m) tam ədədləri verilir. Üçüncü sətirdə pişiyin oturduğu kvadratın koordinatlarını ifadə edən iki x_K və y_K (1 ≤ x_K ≤ n, 1 ≤ y_K ≤ m) tam ədədləri verilir. Dördüncü sətirdə liftin olduğu kvadratların koordinatlarını ifadə edən iki x_E və y_E (1 ≤ x_E ≤ n, 1 ≤ y_E ≤ m) tam ədədləri verilir. Bu üç kvadratlar cütlüyü fərqlidirlər.
Çıxış verilənləri
Çıxış faylının yeganə sətrində minimal addımlar atmaqla heç bir kvadratdan ikinci dəfə keçməməklə pişiyə, sonra da liftə çatmaq üçün üsulların sayını verin. Ədədi 10^9+7 modluna görə vermək lazımdır.
Misalın şərhi
Misalda verilmiş sahəyə görə iki üsul
Nümunə
3 3 1 1 3 3 2 2
2