Có \(N\) người chơi ngồi thành một vòng tròn, được đánh số từ \(1\) đến \(N\) theo chiều chia bài.

Việc chia bài được thực hiện trong \(M\) lần. Ở lần chia thứ \(t\), người được nhận bài sẽ nhận đúng \(t\) lá bài.

Thứ tự người nhận bài lặp lại theo vòng tròn:

• Lần \(1\): người \(1\) nhận \(1\) lá bài;
• Lần \(2\): người \(2\) nhận \(2\) lá bài;
• ...
• Lần \(N\): người \(N\) nhận \(N\) lá bài;
• Lần \(N + 1\): người \(1\) nhận \(N + 1\) lá bài;
• Lần \(N + 2\): người \(2\) nhận \(N + 2\) lá bài;
• ...

Yêu cầu: Sau khi thực hiện xong \(M\) lần chia bài, hãy tính tổng số lá bài mà \(K\) người đầu tiên nhận được. Vì kết quả có thể rất lớn, chỉ cần in ra phần dư của kết quả khi chia cho \(2026\).

Input

• Dòng thứ nhất chứa số tự nhiên \(N\) (\(1 \le N \le 10^9\)).
• Dòng thứ hai chứa số tự nhiên \(M\) (\(1 \le M \le 10^9\)).
• Dòng thứ ba chứa số tự nhiên \(K\) (\(1 \le K \le N\)).

Output

• In ra một số tự nhiên duy nhất là phần dư của tổng số lá bài mà các người chơi từ \(1\) đến \(K\) nhận được sau \(M\) lần chia khi chia cho \(2026\).

Example

3
7
2

19

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(N, M \le 10^5\).
• Subtask \(2\) (\(30\%\) số điểm): Không có ràng buộc bổ sung (\(N, M \le 10^9\)).