Cho xâu \(S\) gồm n kí tự các chữ cái in thường (a đến a). Xét các hoán vị không lặp lại của xâu này. Ví dụ với xâu cbbb cbbb ta sẽ có 4 hoán vị: cbbb, bcbb, bbbc, bbbc.

Yêu cầu: Tìm số lượng chữ số 0 tận cùng của số lượng các hoán vị không lặp của xâu đã cho.

Input

• Dòng 1: chứa số nguyên n \((1 \leq n \leq 10 ^ 4)\).
• Dòng 2: chứa xâu \(S\).

Output

• Ghi một số nguyên là số lượng chữ số 0 tận cùng tìm được.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n\leq15\)
• Subtask \(2\) (\(50\%\) số điểm): \(n \leq 10 ^ 4\)

Example

7 3
1 5 2 3 1 4 1 

5