CaiWinDao có một cái tháp \(N\) tầng. Anh sẽ tô màu mỗi tầng của tháp bằng một trong 3 màu: đỏ, xanh dương, xanh lá hoặc không tô. Đồng thời, anh cũng định nghĩa độ đẹp của tháp như sau:

Độ đẹp của tháp bằng tổng độ đẹp của \(N\) tầng. Trong đó, độ đẹp của tầng màu đỏ là \(A\), xanh là là \(A + B\), xanh dương là \(B\), và \(0\) nếu không được tô. Ở đây, \(A, B\) là các số được cho trước.

CaiWinDao rất thích con số \(40529042905\) nên muốn độ đẹp của cái tháp cũng là \(40529042905\). Tuy nhiên, CaiWinDao cho rằng con số này không có ý nghĩa toán học gì (mà chỉ có ý nghĩa về tinh thần) nên đã thay nó bằng một số \(K\). Anh tự hỏi rằng, có bao nhiêu cách tô màu sao cho độ đẹp của tháp đúng bằng \(K\)? Hai cách tô được xem là khác nhau nếu có một tầng được tô màu khác nhau trong hai cách.

Input

Gồm một dòng chứa bốn số nguyên \(N, A, B, K \ ( 1 \leq N \leq 3 \times 10^5, 1 \leq A,B \leq 3 * 10^5, 0 \leq K \leq 18 \times 10^{10})\)

Output

In ra số cách tô \(mod \ 998244353\)

Example

4 1 2 5

40

2 5 6 0

1

90081 33447 90629 6391049189

577742975

Nguồn: AtCoder