Lì xì đầu năm cho trẻ em và người già là một phong tục phổ biến trong những ngày đầu năm mới của dân tộc ta. Phong bao lì xì là tượng trưng cho sự kín đáo, không so bì hơn thua. Màu đỏ của phong bao lì xì tượng trưng cho màu của như ý, cát tường, thịnh vượng, của niềm hy vọng và sự may mắn. Người được nhận lì xì luôn tin rằng những phong bao này sẽ đem lại hạnh phúc và tài lộc trong suốt cả năm. Ý nghĩa của một bao lì xì không nằm ở giá trị tiền bên trong mà là ở những thông điệp tốt đẹp mà nó gửi gắm, là món quà tinh thần dành cho những người xung quanh.

Tết năm nay, gia đình Mai đã chuẩn bị \(N\) bao lì xì được để theo một thứ tự từ \(1\) đến \(N\), mỗi bao lì xì sẽ chứa một lượng tiền nguyên dương. Để các bao lì xì được ý nghĩa hơn, mẹ của Mai đã quyết định ước chung lớn nhất của lượng tiền bỏ vào trong các bao phải nằm trong khoảng \([A, B]\). Cùng lúc đó, bố của Mai lại muốn bội chung nhỏ nhất của chúng phải nằm trong khoảng \([C, D]\). Vì hai người rất hòa thuận nên họ muốn tìm một số cách bỏ tiền vào các bao lì xì mà thỏa mãn cả hai điều kiện trên rồi chọn ra một cách theo ý họ.

Yêu cầu: Bạn hãy giúp gia đình Mai đếm số lượng cách thỏa mãn. Hai cách được xem là khác nhau khi tồn tại một bao có giá trị tiền khác nhau trong hai cách ở cùng thứ tự.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq N \leq 10^{18}\)) là số lượng bao lì xì.
• Dòng thứ hai chứa hai số nguyên \(A\) và \(B\) (\(1 \leq A \leq B \leq 10^{18}\)) là điều kiện của mẹ Mai.
• Dòng thứ ba chứa hai số nguyên \(C\) và \(D\) (\(1 \leq C \leq D \leq 10^{18}\), \(D \leq A \cdot 10^7\)) là điều kiện của bố Mai.

Output

• Ghi ra một dòng duy nhất chứa một số nguyên là phần dư của số lượng cách bỏ tiền vào các bao lì xì mà thỏa mãn cả hai điều kiện trong phép chia cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N = 2\) và \(D \leq 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N = 2\).
• Subtask \(3\) (\(30\%\) số điểm): \(D \leq A \cdot 10^5\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

2
1 2
5 7

10