題目描述

小K上課時學到了分解質因數，但是小K覺得分解質因數太簡單了，他想把一些數相乘合成一個合數。但是他的計算速度太慢了，你可以寫個程式幫幫他嗎？

輸入格式

 第一行為一個正整數 n ，表示接下來有 n 個數。

第 2 ~ n + 1 行分別有兩個正整數 a_i 和 b_i 

輸出格式

輸出 pow(a₁, b₁) × pow(a₂, b₂) × ... × pow(a_n, b_n) mod 10⁹⁰⁰

Samples

2
2 3
3 2

72

提示

此題乃水題

 

對於所有測試點，保証 n ≤ 1000, a ≤ 2⁶⁴ - 1, b ≤ 2⁶⁴ - 1

對於第一個測試點，保証 n ≤ 10, a ≤ 10, b ≤ 3

對於第二個測試點，保証 n ≤ 10, a ≤ 10, b ≤ 10

對於第三個測試點，保証 n ≤ 20, a ≤ 10, b ≤ 10

對於第四個測試點，保証 n ≤ 10, a ≤ 5, b ≤ 100

對於第五個測試點，保証 n ≤ 20, a ≤ 5, b ≤ 100

對於第六個測試點，保証 n ≤ 20, a ≤ 10, b ≤ 100

對於第七個測試點，保証 n ≤ 1000, a ≤ 10, b ≤ 2 × 10⁹

對於第八個測試點，保証 n ≤ 1000, a ≤ 2 × 10⁹, b ≤ 2 × 10⁹

對於第九個測試點，保証 n ≤ 1000, a ≤ 2 × 10⁹, b ≤ 2⁶⁴ - 1

對於第十個測試點，保証 n ≤ 1000, a ≤ 2⁶⁴ - 1, b ≤ 2⁶⁴ - 1

原始資料

• Zero1 題號：a848
• Hydro 題號：Z0848
• Locale：en_US
• Display：open