Hãy đếm số lượng số \(x\) (\(1 \le x < n\)) \(mod\) \(998244353\) sao cho có chính xác một điều kiện dưới đây thỏa mãn:

• \(x\) là bội của \(3\).
• \(x\) có chứa chữ số \(3\).
• Có chính xác \(3\) chữ số khác nhau được dùng trong \(x\).

Input

• Một số nguyên dương \(n\) (\(1 \le n \le 10^{500}\)).

Output

• Một số nguyên duy nhất là số lượng số \(x\) thỏa mãn yêu cầu đề bài.

Example

45

19