Cho bốn số nguyên dương \(n, k, a\) và \(b\). Hãy đếm số dãy số nguyên dương \(x_{1}, x_{2}, \ldots, x_{n}\) sao cho:

• Với mọi \(1 \leq i \leq n, a \leq x_{i} \leq b\).
• Bội số chung nhỏ nhất của các số \(x_{1}, x_{2}, \ldots, x_{n}\) chia hết cho \(k\).

Do số lượng dãy có thể rất lớn, bạn chỉ cần in ra kết quả theo modulo \(998244353\).

Input

• Gồm một dòng duy nhất chứa bốn số nguyên \(n, k, a\) và \(b\) \((1 \leq n \leq 227,1 \leq k \leq 10^{14}, 1 \leq a \leq b \leq 10^{14})\).

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán nêu trên theo modulo \(998244353\).

Scoring

• Subtask \(1\) (\(7\) điểm): \(k = 1\)
• Subtask \(2\) (\(8\) điểm): \(n \leq 5, b \leq 30\) và \(k \leq 30\).
• Subtask \(3\) (\(9\) điểm): \(n \leq 5\) và \(b - a \leq 30\)
• Subtask \(4\) (\(10\) điểm): \(k\) là số nguyên tố
• Subtask \(5\) (\(16\) điểm): \(b \leq 10^{7}\) và \(k \leq 10^{7}\)
• Subtask \(6\) (\(20\) điểm): Không có ràng buộc gì thêm.

Example

2 6 10 14

9

3 5 7 9

0