Nhật Tăng định nghĩa số giả đối xứng là một số nguyên dương thỏa mãn các điều kiện sau:

• Không có chữ số ~0~ ở đầu.
• Số chữ số là số chẵn.
• Tổng các chữ số của nửa bên trái bằng tổng các chữ số của nửa bên phải.

Ví dụ: Số ~123510~ là một số giả đối xứng vì:

• Số chữ số là ~6~ (chẵn),
• Tổng ~3~ chữ số bên trái: ~1 + 2 + 3 = 6~,
• Tổng ~3~ chữ số bên phải: ~5 + 1 + 0 = 6~.

Yêu cầu: Cho một số nguyên dương ~n~, hãy đếm số lượng số giả đối xứng có độ dài không vượt quá ~n~.

Input

• Một số nguyên dương ~n~ duy nhất ~(1 < n \le 5000)~.

Output

• Một số nguyên duy nhất là số lượng số giả đối xứng có độ dài không vượt quá ~n~ sau khi chia lấy dư cho ~998244353~.

Sample Input

3

Sample Output

9

Notes

• Các số giả đối xứng là: ~11,22,33,44,55,66,77,88,99~.

Ràng buộc

• ~20\%~ số test tương ứng với ~20\%~ số điểm có: ~n \le 10~.
• ~20\%~ số test tương ứng với ~20\%~ số điểm có: ~n \le 100~.
• ~20\%~ số test tương ứng với ~20\%~ số điểm có: ~n \le 350~.
• ~20\%~ số test tương ứng với ~20\%~ số điểm có: ~n \le 1000~.
• ~20\%~ số test tương ứng với ~20\%~ số điểm có: ~n \le 5000~.