Cho ~2~ số nguyên dương ~n~, ~m~ (~n, m \le 10^5~).

Tìm ước chung lớn nhất của số fibonacci thứ ~n~ và số fibonacci thứ ~m~ mod ~10^9+7~ (với ~2~ số fibonacci đầu tiên đều là ~1~(~f[1]=1, f[2]=1~)).

Sample

Input

3 6

Output

2

Giải thích

~f[3]=2, f[6]=8, GCD(2, 8)=2~

Sắp đến sinh nhật của thầy mrtee, các học sinh của tuyển Tin muốn mua tặng thầy một món quà. Sau khi tìm hiểu, họ đã biết được món quà thầy mrtee thích nhưng giá của món quà quá đắt nên lớp trưởng phải phát động một chương trình góp tiền mặt để mua quà tặng.

Tuyển Tin có ~n~ bạn đánh số từ ~1~ tới ~n~, số tiền nhiều nhất mà bạn thứ ~i~ có thể đóng góp là ~a_i~. Lớp trưởng muốn việc quyên góp tiền đạt được những yêu cầu sau:

• Số tiền mỗi người sẽ đóng góp là một số nguyên.
• Không có ai phải trả nhiều hơn khả năng của mình.
• Chênh lệch giữa người góp tiền ít nhất và nhiều nhất là nhỏ nhất có thể.
• Số tiền thu được đúng bằng số tiền để mua quà.

Biết tổng tiền cần có để mua quà và khả năng đóng góp của mỗi người, hãy xác định xem chênh lệch giữa người góp tiền ít nhất và nhiều nhất nhỏ nhất là bao nhiêu.

INPUT

Dòng đầu gồm 2 số nguyên dương ~n~, ~m~ (~n \le 10^5~, ~m \le 10^{18}~) với ~n~ là số người, ~m~ là số tiền cần trả để mua quà.

Dòng thứ hai gồm ~n~ số ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~) lần lượt là số tiền nhiều nhất mà mỗi bạn có thể đóng góp.

OUTPUT

In ra kết quả của bài toán. Nếu không tìm được phương án theo yêu cầu thì in ra ~-1~

SAMPLE INPUT 1

4 20
10 10 4 4

SAMPLE OUTPUT 1

2

Giải thích: Cách quyên góp ~6, 6, 4, 4~

SAMPLE INPUT 2

3 7
1 1 4

SAMPLE OUTPUT 2

-1

Giải thích: Không có cách nào

SAMPLE INPUT 3

5 34
9 8 9 9 4

SAMPLE OUTPUT 3

4

Giải thích: Cách quyên góp ~8, 7, 8, 7, 4~