Bạn cần lát đầy dải ô vuông kích thước \(1 \times N\) bằng các viên gạch có độ dài \(1, 2,\) hoặc \(3\).

• Gạch có độ dài \(1\) có \(a\) màu khác nhau.
• Gạch có độ dài \(2\) có \(b\) màu khác nhau.
• Gạch có độ dài \(3\) có \(c\) màu khác nhau.

Hai cách lát được coi là khác nhau nếu tồn tại ít nhất một ô vuông kích thước \(1 \times 1\) mà viên gạch phủ trên đó khác nhau về độ dài hoặc màu sắc.

Hãy đếm số cách lát đầy dải \(1 \times N\), kết quả lấy dư cho \(998244853\).

Input

• Dòng duy nhất chứa bốn số nguyên dương \(N, a, b, c\) (\(1 \le N \le 10^6, 1 \le a, b, c \le 10^9\)).

Output

• In ra một số nguyên duy nhất là số cách lát dải, lấy dư cho \(998244853\).

Constraints

• \(50\%\) số test có ràng buộc bổ sung: \(N \le 10^3\).
• \(50\%\) số test còn lại không có ràng buộc bổ sung.

Example

3 2 1 1

13