Một phòng thí nghiệm số học đã chế tạo cỗ máy đặc biệt có khả năng tách một số nguyên thành các thừa số nguyên tố.

Cho số nguyên dương N, hãy phân tích N thành tích các thừa số nguyên tố theo thứ tự tăng dần.

• Nếu N là số nguyên tố, in:

N la so nguyen to

Dữ liệu vào

Gồm một dòng duy nhất chứa số nguyên N.

~2 \le N \le 10^9~

Dữ liệu ra

In kết quả theo định dạng:

p1^a1 x p2^a2 x ...

Trong đó:

• ~p1 < p2 < ...~ là các thừa số nguyên tố của N,
• ~ai~ là số mũ tương ứng.

Nếu N là số nguyên tố thì in:

N la so nguyen to

Ví dụ 1

Input

12

Output

2^2 x 3^1

Giải thích

~12=2^2\times3^1~

Ví dụ 2

Input

100

Output

2^2 x 5^2

Ví dụ 3

Input

7

Output

7 la so nguyen to