Hôm nay, bé được học về toán và hình học cơ bản. Bé nghĩ ra trò chơi như sau:

Trên tam giác, bé ghi \(3\) số nguyên dương \(a, b, c\) ở \(3\) đỉnh.

Sau đó, bé lặp đi lặp lại quá trình sau: Trên ba cạnh của tam giác, bé lần lượt viết trên trung điểm của cạnh đó một số có giá trị bằng tổng của \(2\) số ở \(2\) đầu cạnh đấy. Ba số mới được viết này sẽ tạo được một tam giác mới. Bé cứ tiếp tục lặp lại quá trình trên với tam giác mới tạo được.

Để rõ hơn, em hãy xem hình minh họa với \(a = 1, b = 2, c = 3\) và bé đã thực hiện quá trình trên \(2\) lần:

Bé thắc mắc: sau khi thực hiện quá trình trên \(n\) lần thì tổng ba số trên đỉnh của tam giác vừa mới tạo được bằng bao nhiêu?

Vì tổng có thể rất lớn, hãy in ra kết quả sau khi chia lấy dư cho \(2004010501\).

Input

• Một dòng duy nhất chứa 4 số \(a, b, c, n\) (\(1 \le a, b, c \le 100\), \(1 \le n \le 10^9\)).

Output

• Một dòng duy nhất chứa đáp án (theo modulo \(2004010501\)).

Example

1 2 3 2

24

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^4\).
• Subtask \(2\) (\(60\%\) số điểm): \(n \le 10^9\).