Tại Vietnam Game Awards ~2024~, VNGGames một lần nữa được vinh danh nhà phát hành game xuất sắc của năm sau khi trải qua ~2~ vòng thi và nhận được hơn ~38000~ lượt bình chọn từ cộng đồng. Để đáp lại tình cảm từ người hâm mộ, trong lễ trao giải VNGGames đã công bố một trò chơi mini dành cho người hâm mộ của mình. Tại đây VNGGames sẽ thách đố người hâm mộ tìm ra con số ~X~ đã bị mã hoá thành giá trị ~C \equiv X^3 \pmod N~ với ~N~ là một giá trị lớn, có giá trị bằng tích của ~p_1, p_2, p_3, ..., p_K~. Trong đó các giá trị ~p_i~ là những số nguyên tố.

Là một fan hâm mộ nhiệt thành của VNGGames, bạn rất hứng thú với mini game này và quyết tâm trở thành người có thể tìm ra ~X~ trong thời gian ngắn nhất. Lúc này, với tư duy lập trình đã có của mình, bạn dự định sẽ viết chương trình để máy tính có thể giúp bạn tìm ra số ~X~ trong thời gian nhanh nhất có thể.

Input

Chương trình của bạn sẽ lấy Dữ liệu đầu vào (Input) từ những thông tin VNGGames đã cho bạn bao gồm:

• Dòng đầu tiên cho số nguyên dương ~K~, là số lượng ~p_i~.
• Dòng tiếp theo chứa ~K~ số nguyên ~p_i~
• Dòng cuối cùng cho số ~C \pmod N~

Output

• Bạn sẽ viết chương trình yêu cầu máy tính cho dữ liệu đầu ra (Output) là giá trị ~X~ tìm được.

Constraints

• ~3 \leq K \leq 100~
• ~10^6 \leq p_i \leq 10^9~, ~p_i~ là số nguyên tố.
• ~X \leq 10^6 \ll N~
• ~C \lt N~

Sample input

3
1108819 1108823 1108867
1881365963625

Sample output

12345

Giải thích ví dụ

• Ta có ~N = 1108819\times 1108823\times 1108867 = 1363334245757698079~
• Ta thấy được với ~X = 12345~ thỏa được ~C \equiv X^3 \pmod N~