Tek ortak koridor

Bir şehir, $h$ satır ve $w$ sütundan oluşan dikdörtgen bir tablo ile temsil edilir. Satırlar yukarıdan aşağıya, sütunlar soldan sağa numaralandırılır. Her hücre ya boştur ya da engellidir.

İki kuryenin şehri geçmesi gerekir. Bir adımda her kurye, sağdaki veya aşağıdaki komşu boş hücreye geçebilir.

Birinci kurye $(1,a)$ hücresinden başlar ve $(c,w)$ hücresinde bitirmelidir. İkinci kurye $(b,1)$ hücresinden başlar ve $(h,d)$ hücresinde bitirmelidir.

İki rota, ortak hücreleri her iki rotanın da en az iki hücre içeren tek bir bitişik parçasını oluşturuyorsa uyumlu olarak adlandırılır. Bu ortak parça dönüşler içerebilir.

Biçimsel olarak, her iki rotada da bulunan ve aşağıdaki koşulları sağlayan iki farklı $u$ ve $v$ hücresi var olmalıdır:

• $u$ hücresinden önce rotaların ortak hücresi yoktur.

• $u$ hücresinden $v$ hücresine kadar, bu hücreler dâhil, kuryeler tam olarak aynı hücre dizisini ziyaret eder.

• $v$ hücresinden sonra rotaların ortak hücresi yoktur.

Dolayısıyla yalnızca tek bir hücrede buluşmak yeterli değildir. Ayrılıp daha sonra tekrar buluşan rotalar da uyumlu değildir.

Uyumlu rota çiftlerinin sayısını 10^9+7 modunda bulun. Kuryeler birbirinden farklıdır: bir çift, birinci kuryenin rotasını ve ikinci kuryenin rotasını belirler.