Mùa xuân đến rồi đó! Trên bầu trời xanh, các chú chim đang nối đuôi nhau bay về sau ngày dài trú bão. Thoạt nghe tiếng kêu ríu rít của đàn chim, Chương tò mò chạy ra sân đứng ngắm. Đàn chim mỗi lúc xuất hiện càng đông. Chương chợt liên tưởng ngay đến bài học lũy thừa và số nguyên tố sáng hôm nay mà thầy giáo đã dạy. Cậu ấy thiết nghĩ, nếu thử tính con chim lớn nhất trong đàn lũy thừa tần suất xuất hiện của nó liệu có được không.
Với khả năng lập trình tốt, bạn hãy giúp Chương tìm ra kết quả mà cậu ấy muốn. Được biết, tượng trưng cho đàn chim bay về là xâu ký tự \(st\), bao gồm ký tự chữ cái thường và ký tự số; hai số tự nhiên \(a, n\) lần lượt là số lớn nhất hay là dãy con chứa các ký tự số liên tiếp trong xâu st tương ứng với chú chim lớn nhất trong đàn và tần suất xuất hiện của nó. Ở cuối mỗi xâu khi kết thúc luôn kèm theo một ký tự bất kỳ (\(1 ≤ a ≤ 10^6\), xâu \(st\) không quá \(10^6\) ký tự).
Gọi \(S\) là lũy thừa \(a^n\), \(P\) là \(a!\) (\(!\): giai thừa), phân tích \(P\) thành thừa số nguyên tố theo thứ tự thừa số nguyên tố tăng dần.
\(a! = P_1^{x_1} P_2^{x_2} …P_m^{x_m}\).
Ví dụ: \(4^2 = 16,\)
\(4! = 2^3. 3^1\)

Yêu cầu:
Với xâu \(st\) đã cho, hãy tính \(S\) và \(P\).

Input:

• Gồm xâu ký tự chỉ chứa các con số và chữ cái.

Output:

• Dòng thứ nhất là kết quả của \(S\). (\(S\) có thể lớn nên kết quả của bài toán chia dư cho \(10^9+7\));
• Các dòng tiếp theo là số nguyên tố và số mũ tương ứng của nó (các số cách nhau một khoảng trắng).

Ví dụ:

Input:

kythihocsinhgioichuyendot2lanthu4co4thisinhduthi

Output:

16
2 3
3 1 

• Có 50% test tương ứng 50% số điểm của bài với \(1 ≤ a ≤ 10\), độ dài xâu \(st\) không quá \(255\) ký tự;
• Có 50% test tương ứng 50% số điểm của bài với \(a ≤ 10^6\), độ dài xâu \(st\) không quá \(10^6\) ký tự.