Cốc và chìa khoá

Có ba chiếc cốc giống hệt nhau xếp thành một hàng từ trái sang phải. Ban đầu, một chiếc chìa khoá được đặt dưới chiếc cốc ở giữa.

Ở mỗi lượt, người chơi tráo chiếc cốc ở giữa với một trong hai chiếc cốc còn lại, mỗi chiếc được chọn với xác suất bằng nhau ($\frac{1}{2}$); chiếc cốc được chọn sẽ trở thành chiếc cốc ở giữa. Trò chơi diễn ra trong $n$ lượt, mỗi lượt chọn độc lập với các lượt khác. Chìa khoá luôn nằm yên trong chiếc cốc chứa nó lúc đầu (nó chỉ di chuyển theo cốc khi cốc bị tráo).

Sau lượt thứ $n$, ta đoán rằng chìa khoá đang nằm dưới chiếc cốc ở giữa. Hãy tính xác suất đoán đúng.

Số lượt $n$ có thể rất lớn nên không được cho trực tiếp. Thay vào đó, bạn được cho một dãy $a_1,a_2,\dots ,a_k$ và $n$ bằng tích của tất cả các phần tử trong dãy: $$n=a_1·a_2\cdots a_k.$$

Vì lý do độ chính xác, hãy in kết quả dưới dạng một phân số tối giản. Cụ thể, tìm phân số $p/q$ với $gcd(p,q)=1$, rồi in phần dư của $p$ và $q$ khi chia cho ${10}^9+7$.

Lưu ý: điều kiện $gcd=1$ áp dụng cho $p$ và $q$ gốc (trước khi lấy phần dư), không phải cho phần dư của chúng.

Dữ liệu vào

• Dòng đầu chứa số nguyên $k$, số phần tử của dãy.
• Dòng thứ hai chứa $k$ số nguyên $a_1,a_2,\dots ,a_k$.

Dữ liệu ra

In ra một dòng duy nhất dạng x/y, trong đó x là phần dư của $p$ chia ${10}^9+7$ và y là phần dư của $q$ chia ${10}^9+7$.

Ràng buộc

• $1\le k\le {10}^5$
• $1\le a_i\le {10}^{18}$

Ví dụ