You are given an integer and a sequence of integers . Your task is to determine the number of integer sequences such that the following conditions are satisfied:
for each ( ).
is a factor of for each ( ).
Two sequences are considered different if they differ in at least one position.
Since the number of such sequences may be large, compute the answer modulo .
输入格式
The first line of input contains a single integer ( ).
The second line contains integers ( ).
输出格式
Output the number of distinct sequences satisfying the conditions, modulo .
样例
样例输入 1
2
2 4
样例输出 1
6
样例输入 2
6
265 9801 192168 200000 192018 199809
样例输出 2
16555779
数据范围与提示
Explanation for the sample input/output #1
The following are all sequences satisfying the conditions: , , , , , and .
