eolymp
bolt
Try our new interface for solving problems
Məsələlər

Pişiyi xilas etməli

Pişiyi xilas etməli

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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 nm (2n, m100) natural ədədləri ehtiva edir.

İkinci sətirdə Arturun olduğu cari kvadratın koordinatlarını ifadə edən iki x_Ay_A (1x_An, 1y_Am) tam ədədləri verilir. Üçüncü sətirdə pişiyin oturduğu kvadratın koordinatlarını ifadə edən iki x_Ky_K (1x_Kn, 1y_Km) tam ədədləri verilir. Dördüncü sətirdə liftin olduğu kvadratların koordinatlarını ifadə edən iki x_Ey_E (1x_En, 1y_Em) 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ə

Giriş verilənləri #1
3 3
1 1
3 3
2 2
Çıxış verilənləri #1
2
Mənbə XIII All-Russian Olympiad schoolchildren team programming