Bir ortaq dəhliz

Şəhər $h$ sətirdən və $w$ sütundan ibarət düzbucaqlı cədvəl şəklindədir. Sətirlər yuxarıdan aşağıya, sütunlar isə soldan sağa nömrələnir. Hər xana ya boşdur, ya da bağlıdır.

İki kuryer şəhərdən keçməlidir. Hər addımda kuryer sağda və ya aşağıda yerləşən qonşu boş xanaya keçə bilər.

Birinci kuryer $(1,a)$ xanasından başlayır və $(c,w)$ xanasına çatmalıdır. İkinci kuryer $(b,1)$ xanasından başlayır və $(h,d)$ xanasına çatmalıdır.

İki marşrut o zaman uyğun adlanır ki, onların ortaq xanaları hər iki marşrutun ən azı iki xanadan ibarət vahid kəsilməz hissəsini təşkil etsin. Bu ortaq hissədə dönmələr ola bilər.

Formal olaraq, hər iki marşruta daxil olan iki müxtəlif $u$ və $v$ xanası mövcud olmalı və aşağıdakı şərtlər ödənməlidir:

• $u$ xanasına qədər marşrutların ortaq xanası olmasın;

• $u$ və $v$ daxil olmaqla, onların arasında hər iki kuryer eyni xana ardıcıllığı ilə hərəkət etsin;

• $v$ xanasından sonra marşrutların ortaq xanası olmasın.

Beləliklə, yalnız bir xanada görüşmək kifayət deyil. Ayrıldıqdan sonra yenidən görüşən marşrutlar da uyğun deyil.

Uyğun marşrut cütlərinin sayını 10^9+7 moduluna görə tapın. Kuryerlər fərqlidir: cüt birinci kuryerin və ikinci kuryerin marşrutunu müəyyən edir.