#2351 어려운 곱셈 문제

10  1 s   128 MB  

Description

간단하다.

N개의 정수가 입력으로 주어진다. 이 정수들을 모두 곱한 결과를 출력하시오.

Input

첫 줄에는 정수의 수 $N(1 \leq 10,000)$이 주어진다.

그 후 N줄에 걸쳐 한 줄에 하나씩 곱할 정수가 주어진다. 모든 정수는 $[0, 10 ^{100}]$ 의 범위에 속한다.

Output

모든 정수를 곱한 결과를 출력한다. 단, 결과가  $10^9$이상 인 경우, 결과를 $10^9$로 나눈 나머지만 출력한다.

Sample Input

Sample Output

5
2
3
4
5
1
120

HINT

$(a * b )$ % $m$ =  ( (a  % m) * (b%m) ) % m

Source

김동이 (mitslll, 아주대학교)