Một nhà máy có hai loại nguyên liệu: ~P~ và ~Q~. Nhà máy nhận được đơn hàng sản xuất ~n~ loại sản phẩm, trong đó sản phẩm loại ~i~ cần:

• ~a_i~ nguyên liệu loại ~P~.

• ~b_i~ nguyên liệu loại ~Q~.

Nhà máy hiện có ~A~ đơn vị nguyên liệu loại ~P~ và ~B~ đơn vị nguyên liệu loại ~Q~. Mỗi sản phẩm có thể được sản xuất nhiều lần, nhưng nguyên liệu không được lãng phí – tức là nhà máy muốn tận dụng hết nguyên liệu ~P~ và ~Q~ hiện có.

Yêu cầu: Đếm số cách sản xuất sản phẩm sao cho tận dụng hết toàn bộ nguyên liệu loại ~P~ và ~Q~ một cách chính xác.

Input

• Dòng đầu tiên có ba số nguyên ~n~, ~A~ và ~B~ ~(1 \le n \le 10)~; ~(1 \le A, B \le 10^9)~.

• ~n~ dòng tiếp theo, mỗi dòng có hai số nguyên ~a_i~ và ~b_i~ ~(1 \le a_i, b_i \le 5)~.

Output

Số cách sản xuất các sản phẩm tận dụng hết nguyên liệu chia lấy dư cho ~10^9~.

Scoring

Sample Input 1

3 3 3
1 1
2 2
3 3

Sample Output 1

3

Notes

• Một cách sản xuất sản phẩm được biểu diễn bằng một dãy ~n~ số nguyên không âm ~(x_1, x_2, \dots, x_n)~, trong đó ~x_i~ là số lượng sản phẩm thứ ~i~ được sản xuất.

• Hai cách sản xuất ~(x_1, x_2, \dots, x_n)~ và ~(y_1, y_2, \dots, y_n)~ được gọi là khác nhau nếu tồn tại ~k~ sao cho ~x_k \ne y_k~ với ~k = 1, \dots, n~.