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: số cách lát dải, lấy dư cho ~998244853~.

Scoring

Sample Input 1

3 2 1 1

Sample Output 1

13

Notes

Ba gạch độ dài 1: ~2^3 = 8~ cách.

Gạch độ dài 1 + gạch độ dài 2: ~2 \times 1 = 2~ cách.

Gạch độ dài 2 + gạch độ dài 1: ~1 \times 2 = 2~ cách.

Một gạch độ dài 3: 1 cách.

Tổng = ~8 + 2 + 2 + 1 = 13~.