Đề bài

Viết chương trình phân tích một số nguyên dương \( n \) (với \( 2 \leq n \leq 10^{12} \)) thành các thừa số nguyên tố. Chương trình cần in ra kết quả dưới dạng:

• \( n = p_1^{e_1} \times p_2^{e_2} \times \dots p_m^{e_m}\), với \( p_i \) là các thừa số nguyên tố và \( e_i \) là số mũ tương ứng.

Input

• Một dòng duy nhất chứa số nguyên \( n \).

Output

• Dòng duy nhất là biểu diễn phân tích thừa số nguyên tố của \( n \). Chú ý định dạng của phân tích như test mẫu. Trước và sau dấu bằng có dấu cách trống, trước và sau dấu nhân ” * ” có dấu cách trống.

Ví dụ

Input

60

Output

60 = 2^2 * 3^1 * 5^1

Gợi ý

• Sử dụng thuật toán chia dần (đếm số lần chia hết cho từng số nguyên tố, các số từ i chạy từ 2 trở đi nếu n chia hết chi i thì tiến hành chia cho i ra khỏi n cho tới khi không chia được nữa và đếm số mũ tương ứng).
• Các thừa số nguyên tố phải được sắp xếp theo thứ tự tăng dần.

Giới hạn

1. Subtask 1: \( n \leq 10^6 \).

2. Subtask 2: \( 10^6 < n \leq 10^{12} \).