Nhân dịp vừa bước sang năm mới dương lịch 2026, hai tổ chức CLAOJ và DEVGANG hợp tác tổ chức Contest Chào Năm Mới — một sự kiện được giới thiệu là nhẹ nhàng, vui vẻ, ai cũng có thể tham gia để lấy lộc đầu năm. Thông báo là vậy, nhưng những người quen với CLAOJ đều hiểu: nhẹ nhàng thường chỉ đúng với tiêu đề.

Trong lúc nhiều người còn đang đếm ngược số ngày nghỉ Tết, Rùa Biển bất ngờ nhận được một phong thư đỏ rực từ Gấu Tuyết — cao thủ lập trình của CLAOJ, người có sở thích khiến người khác… đọc thiếu một dòng.

Trên phong thư có ghi:

Lì xì đầu năm – nhận càng nhiều, lộc càng lớn.

Bên trong không có tiền, chỉ có đường link và một dòng chữ nhỏ:

Đi hết là có quà.

Trang web mở ra với tiêu đề:

Hành Trình Vượt Vũ Môn – Hái Lộc Khai Xuân 2026

Ngay bên dưới, hệ thống giới thiệu:

Rùa Biển sẽ đi qua một số trạm và nhận lì xì ở mỗi trạm.

Gấu Tuyết lập tức nhắn thêm:

Contest CLAOJ x DEVGANG sắp mở rồi. Xong phần này là vào thi ngay. Bài này dễ, chỉ là cộng thôi.

Rùa Biển chưa kịp nghi ngờ thì giao diện đã chuyển sang bản đồ. Một con đường dài hiện ra, với các trạm được đánh số bắt đầu từ 0.

Ở phần hướng dẫn, hệ thống viết rất rõ (chia thành nhiều dòng):

• Tại trạm số 0, Rùa Biển nhận được ~A~ đồng.
• Mỗi trạm tiếp theo, số tiền tăng thêm đúng ~X~ đồng so với trạm trước đó.
• Quy tắc này áp dụng đến trạm ~N~.

Ngay bên dưới là một dòng chữ tô đậm:

Tại trạm ~N~, số tiền nhận được là ~A + N*X~.

Ở phía dưới, nhỏ hơn, có thêm câu:

Rùa Biển phải đi qua và nhận tiền ở tất cả các trạm.

Trong suốt hành trình, giao diện liên tục hiện những gợi ý:

• Số tiền đang tăng đều.
• Công thức rất quen thuộc.
• Bạn đã đến trạm cuối.

Ở trạm ~N~, hệ thống hiện dòng chữ:

Bạn đã nhận được số tiền lớn nhất trên hành trình.

Rùa Biển suýt nữa tin rằng mọi thứ đã xong. Nhưng khi nhấn "Hoàn thành", một cánh cổng bảo mật bất ngờ xuất hiện cùng dòng chữ:

Nhập mật mã để vào Contest Chào Năm Mới CLAOJ x DEVGANG

Gấu Tuyết nói:

Mật mã là tổng số tiền ~S~ mà bạn đã gom được. Nhưng hệ thống chỉ cần ~S \mod M~ thôi.

Do Rùa Biển có tính ẩu, nên đã nhập sai vài lần và phải bắt đầu lại. Nhiệm vụ của các bạn là tìm ra mật mã để tham gia contest. Biết rằng ~M = 998244353~.

Dữ liệu vào

Gồm ~1~ dòng chứa ~3~ số nguyên ~N~, ~A~, ~X~ (~1 \leq N, A, X \leq 10^{18}~), cách nhau bởi ~1~ dấu cách.

Dữ liệu ra

Ghi ra tổng số tiền Rùa Biển nhận được modulo ~M~.

Ví dụ

Đầu vào

3 2 1

Đầu ra

14

Giải thích

Số tiền nhận được ở các trạm ~0, 1, 2, 3~ lần lượt là ~2, 3, 4, 5~, tổng ~S = 2 + 3 + 4 + 5 = 14 \mod 998244353 = 14~.

Tính điểm

• Subtask ~1~ ~(30~ điểm~): 1 \leq N, A, X \leq 10^6.~
• Subtask ~2~ ~(30~ điểm~): 1 \leq N, A, X \leq 10^9.~
• Subtask ~3~ ~(40~ điểm~): 1 \leq N, A, X \leq 10^{18}.~