Maraqların toqquşması
Kopatıç maşını ilə Pinin növbəti mexanizminə çırpıldıqdan sonra, Pin əsəbiləşdi və Şmeşariklərin toplantısında torpaq istifadəsi üçün yeni qaydalar təyin etdi. İndi hər bir Şmeşarik, Şmeşariklər ölkəsinin hər hansı bir sahəsini istifadə etmək istədikdə, onu Yojikin saxladığı xüsusi kitabçaya bəyan etməlidir. Şmeşariklər ölkəsini şaquli tərəfi H və üfüqi tərəfi W olan bir dama taxtası şəklində təsəvvür etmək olar.
Ertəsi gün saat 8:01-də Yojikin qapısına eyni anda Sovunya və Nyusha gəldi: Sovunya idman meydançası üçün yer ayırmaq istəyirdi, Nyushaya isə kordebalet məşqləri üçün zona lazım idi.
Mübahisələrin qarşısını almaq üçün Yojik Nyusha və Sovunyaya əvvəlcədən hansı sahənin kimə lazım olduğunu razılaşmalarını və yalnız bundan sonra kitabçaya yazılmalarını söylədi. O, həmçinin bəzi qaydalar təyin etdi:
Hər iki sahə Şmeşariklər ölkəsinin boş olmayan alt-düzbucaqları olmalıdır.
Hər bir düzbucağın hündürlüyü h-dan, eni isə w-dan çox ola bilməz.
Düzbucaqlar ümumi hüceyrələrə malik olmamalıdır (amma toxuna bilərlər).
İndi Sovunya və Nyusha Yojikin evində xəritənin qarşısında dayanıb, iki düzbucağı necə seçə biləcəklərini düşünürlər. Yojikə bu şəxsi sərhəd pozuntusunun nə qədər uzanacağını qiymətləndirməyə kömək edin və göstərilən məhdudiyyətlərə cavab verən iki düzbucağı seçmək üçün neçə yol olduğunu tapın. Bu rəqəm kifayət qədər böyük ola bilər, ona görə də onu 10^9 + 7 moduluna görə hesablayın.
Giriş məlumatları
Birinci sətirdə iki tam ədəd H və W (1 ≤ H, W ≤ 10^9) - Şmeşariklər ölkəsinin hündürlüyü və eni verilir. İkinci sətirdə iki tam ədəd h və w (1 ≤ h, w ≤ 3 * 10^5, h ≤ H, w ≤ W) - düzbucaqların icazə verilən maksimum hündürlüyü və eni verilir.
Çıxış məlumatları
Bir tam ədəd - Sovunya və Nyushanın idman meydançası və kordebalet zonası üçün yer seçmək yollarının sayının 10^9 + 7-yə bölünməsindən alınan qalığı çıxarın.
Qeyd
Birinci nümunədə Şmeşariklər ölkəsi yalnız bir hüceyrədən ibarətdir və hər biri ən azı bir hüceyrə olan iki kəsişməyən düzbucağı yerləşdirmək mümkün deyil.
Aşağıdakı şəkildə ikinci nümunədə idman meydançasını (qırmızı düzbucaq) və kordebalet zonasını (yaşıl düzbucaq) yerləşdirmək üçün 35 yol göstərilmişdir. Rəngləri dəyişməklə qalan 35 yol əldə olunur.
Üçüncü nümunədə dəqiq 119 493 408 836 453 856 = (10^9 + 7) * 119 493 408 yol var, belə ki, cavab 0.