Khu phố CSUH có ~N~ căn nhà nằm liền kề dọc theo tuyến đường chính, được đánh số từ ~1~ đến ~N~. Ban quản lý khu phố muốn tiến hành sơn các căn nhà sao cho mỗi căn nhà chỉ được sơn đúng một trong bốn màu: trắng, đỏ, lam hoặc lục.

Điểm thẩm mỹ của một căn nhà được xác định dựa trên màu sơn của căn nhà đó: Trắng ~=0~ điểm, Đỏ ~= A~ điểm, Lam ~=B~ điểm và Lục ~=A+B~ điểm. Ban quản lý khu phố muốn lập kế hoạch sơn các căn nhà sao cho tổng điểm thẩm mỹ của ~N~ căn nhà bằng chính xác ~K~.

Nhiệm vụ của bạn hãy đếm số cách sơn các căn nhà sao cho tổng điểm thẩm mỹ của các căn nhà bằng ~K~. Lưu ý rằng hai cách sơn nhà được xem là khác nhau nếu có một căn nhà được sơn màu khác nhau ở hai cách.

Input

• Dòng duy nhất chứa bốn số nguyên ~N~, ~A~, ~B~, ~K~ ~(1 \le N,A,B \le 3.10^5\;;~ ~0 \le K \le 2.10^{11})~.

Output

• In ra số cách sơn nhà thỏa mãn điều kiện đề bài với kết quả chia lấy dư cho ~998244353~.

Examples

Sample Input

4 1 2 3

Sample Output

20

Scoring

• Subtask ~1~ với ~50\%~ số điểm: ~N \le 2000~
• Subtask ~2~ với ~50\%~ số điểm: Không có ràng buộc gì thêm

Notes

Ở ví dụ, màu đỏ tương ứng ~1~ điểm, màu lam tương ứng ~2~ điểm và màu lục tương ứng ~1+2=3~ điểm. Các cách chọn màu như sau:

• Hai màu trắng, một màu đỏ, một màu lam: Có ~12~ cách sơn.
• Một màu trắng, ba màu đỏ: Có ~4~ cách sơn.
• Ba màu trắng, một màu lục: Có ~4~ cách sơn.

Vì vậy có tổng cộng ~12+4+4=20~ cách sơn nhà thỏa mãn.