Trận Bóng Bàn

Trong một buổi giao lưu thể thao, FullHouse Dev được mời đến xem một trận bóng bàn thú vị. Họ gặp một vận động viên đang ghi chép điểm số của trận đấu và đưa ra một thử thách toán học thú vị về cách tính điểm có thể xảy ra trong trận đấu.

Bài toán

Trong một trận bóng bàn, điểm số được ghi theo dạng "\(p1:p2\)" trong đó \(p1\) là điểm của người chơi 1 và \(p2\) là điểm của người chơi 2. Trận đấu bắt đầu từ 0:0. Khi người chơi 1 ghi điểm, tỉ số sẽ thành \(p1+1:p2\), và ngược lại khi người chơi 2 ghi điểm, tỉ số sẽ thành \(p1:p2+1\). Trận đấu kết thúc khi một trong hai người chơi đạt ít nhất 11 điểm và hơn đối thủ đúng 2 điểm.

FullHouse Dev được cung cấp hai tỉ số: tỉ số ban đầu \(X1:Y1\) và tỉ số kết thúc \(X2:Y2\). Nhiệm vụ là tính số cách có thể để đạt được tỉ số cuối cùng từ tỉ số ban đầu, tuân theo luật bóng bàn.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Mỗi test case gồm một dòng chứa 4 số nguyên \(x1\), \(y1\), \(x2\), \(y2\) cách nhau bởi dấu cách, trong đó \((x1,y1)\) là tỉ số ban đầu và \((x2,y2)\) là tỉ số kết thúc

OUTPUT FORMAT:

• Với mỗi test case thứ \(i\), in ra "Case i: x" trong đó x là số cách có thể đạt được tỉ số cuối HOẶC "-1" nếu tỉ số cuối không hợp lệ
• Kết quả được tính theo modulo \(10^9 + 9\)

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(0 \leq x1 \leq x2 \leq 30\)
• \(0 \leq y1 \leq y2 \leq 30\)

Ví dụ

INPUT

2
6 9 11 9
10 11 14 12

OUTPUT

Case 1: 1
Case 2: 2

Giải thích

• Test case 1: Người chơi 2 không ghi thêm điểm nào. Tất cả các điểm sau tỉ số ban đầu đều do người chơi 1 ghi được. Chỉ có một cách duy nhất để điều này xảy ra.

• Test case 2: Từ tỉ số 10:11, có hai cách để đạt được tỉ số 14:12:

  1. 10:11 -> 11:11 -> 12:11 -> 12:12 -> 13:12 -> 14:12
  2. 10:11 -> 11:11 -> 11:12 -> 12:12 -> 13:12 -> 14:12

  Hai cách này được coi là khác nhau vì tại điểm thứ 23 của trận đấu, tỉ số khác nhau (12:11 và 11:12).