Một chuỗi con được gọi là khác biệt nếu mỗi chữ cái trong đó xuất hiện không quá một lần. Kem thích chơi với các từ theo cách sau: Cậu lấy một từ và tách nó thành các chuỗi con khác biệt.

Ví dụ: từ abba có thể được tách thành các chuỗi con khác biệt theo \(4\) cách:

• a b b a
• ab b a
• a b ba
• ab ba

Tuy nhiên, Kem không phải lúc nào cũng có thể tách từ đúng. Hãy giúp cậu đếm tất cả các cách chia từ \(s\) thành các chuỗi con khác biệt. Các chuỗi con trong cách tách không được để trống.

In số cách tách thỏa mãn (theo modulo \(998244853\)).

Input

• Dòng đầu ghi từ \(s\). (Từ \(s\) chỉ chứa các chữ cái tiếng Anh in thường, \(|s| \le 10^5\)).

Output

• In ra số cách tách một từ thành các chuỗi con khác biệt theo modulo \(998244853\).

Example

abcbca

20

abba

4

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(|s| \le 1000\).
• Subtask \(2\) (\(40\%\) số điểm): \(|s| \le 10^5\).