Bạn được cho một số nguyên $N$ được biểu diễn ở hệ thập phân.
Xét tất cả các số nguyên có thể được tạo thành bằng cách sắp xếp lại các chữ số của $N$ sao cho số thu được không có chữ số $0$ đứng đầu (leading zeros).
Hãy tìm số lượng các số nguyên như vậy chia hết cho $11$, lấy phần dư theo modulo $2147483647$ ($= 2^{31} - 1$), là một số nguyên tố.
Lưu ý rằng các số nguyên được tạo thành bằng cách sắp xếp lại các chữ số của $N$ bao gồm cả chính $N$.
Dữ liệu vào
Dữ liệu vào được cho theo định dạng sau:
$$N$$
- Tất cả các giá trị đầu vào đều là số nguyên.
- $1 \le N < 10^{2 \times 10^6}$
- $N$ được cho ở hệ thập phân không có chữ số $0$ đứng đầu.
Kết quả
In ra câu trả lời trên một dòng duy nhất.
Ví dụ
Dữ liệu vào 1
1001
Kết quả 1
2
Dữ liệu vào 2
31415926535
Kết quả 2
144000
Giải thích
Trong ví dụ thứ nhất, $1100$ và $1001$ thỏa mãn điều kiện.