Xí nghiệp Zeta chuyên sản xuất ~m~ loại sản phẩm. Để sản xuất ~m~ loại sản phẩm này cần sử dụng hai loại nguyên liệu chính ~\mathrm{P}~ và ~\mathrm{Q}~. Để sản xuất một sản phẩm ~i (i = 1, 2, ..., m)~ cần ~a_i~ đơn vị nguyên liệu loại ~P~ và ~b_i~ đơn vị nguyên liệu loại ~\mathrm{Q}~. Hiện tại trong kho của xí nghiệp có ~A~ đơn vị nguyên liệu loại ~\mathrm{P}~ và ~B~ đơn vị nguyên liệu loại ~\mathrm{Q}~. Ban giám đốc cần lập phương án sản xuất tận dụng hết ~A~ đơn vị nguyên liệu loại ~\mathrm{P}~ và ~B~ đơn vị nguyên liệu loại ~\mathrm{Q}~. Phương án sản xuất của xí nghiệp được mô tả bởi dãy ~x=(x_1, x_2, ..., x_m)~, trong đó ~x_i~ là số lượng sản phẩm loại ~i~ sẽ sản xuất (~x_i~ là số nguyên không âm), ~i = 1, 2, ..., m~. Hai phương án sản xuất ~x=(x_1, x_2, ..., x_m)~, và ~y=(y_1, y_2, ..., y_m)~ được gọi là khác nhau nếu tồn tại ít nhất một chỉ số ~k (1 \le k \le m)~ sao cho ~x_k \ne y_k~.

Yêu cầu: Cho ~a_i, b_i (i = 1, 2, ..., m)~ tương ứng là lượng nguyên liệu loại ~\mathrm{P}~, ~\mathrm{Q}~ cần thiết để sản xuất một sản phẩm ~i~ và ~A, B~ là lượng nguyên liệu loại ~\mathrm{P}~, ~\mathrm{Q}~ có trong kho. Hãy tính ~N~ là số lượng phương án sản xuất khác nhau tận dụng hết ~A~ nguyên liệu loại ~\mathrm{P}~, ~B~ nguyên liệu loại ~\mathrm{Q}~.

Dữ liệu:

• Dòng thứ nhất chứa ba số nguyên dương ~m, A~ và ~B~ tương ứng là số loại sản phẩm, số lượng nguyên liệu loại ~\mathrm{P}~ và loại ~\mathrm{Q}~ có trong kho (~m \le 10~);
• Dòng thứ ~i~ trong số ~m~ dòng tiếp theo chứa hai số nguyên dương ~a_i~ và ~b_i (a_i, b_i \le 5)~ tương ứng là lượng nguyên liệu loại ~\mathrm{P}~ và ~\mathrm{Q}~ cần thiết để sản xuất một sản phẩm ~i ( i = 1, 2, ..., m)~.

Kết quả:

• Ghi ra số nguyên ~N \% 10^9~, trong đó ~N~ là số phương án sản xuất khác nhau tận dụng hết hai loại nguyên liệu tìm được, ~\%~ là phép toán chia lấy dư.

Ràng buộc:

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài có ~A, B \le 100~;
• Có ~30\%~ số test khác ứng với ~30\%~ số điểm của bài có ~A, B \le 1000~;
• Có ~40\%~ số test còn lại ứng với ~40\%~ số điểm của bài có ~A, B \le 10^9~.

Ví dụ:

Sample Input

3 3 3
1 1 
2 2 
3 3

Sample Output

3