Thanks to Clive Fraser for creating this problem!
Rotas have a fixed cycle length. Typically this is a number of days. The rota can be a list of people, activities, jobs etc. When the last day of the cycle has passed the rota is repeated and this continues indefinitely until the rota is changed.
An organisation can have several rotas, each with a different cycle length. It is convenient to display these on a common rota board so that people can see what is prescribed for each of the rotas on any particular day. The rotas are displayed in separate columns on the rota board. Rows on the board represent individual days. The top row on the board represents the first day for each of the rotas. The bottom row on the board represents the last day for each of the rotas. This is only possible if the number of rows on the board represents a whole number of cycles for each of the rotas.
Bob has a business making rota boards. These have the rota cycles marked on them and provide clear windows at each entry position so that removable cards can be used to provide the description for that day in the rota. The rota boards made by Bob have at least two different rota cycles on them. In fact Bob has found that there are N different commonly used rota cycle lengths. His aim is to make a rota board for every possible combination of rota cycles from this list. This means that any given rota board will contain between 2 and N of these rotas. The length of the rota board is the number of rows on the board. Bob wants to minimise the board length so he always chooses the smallest length which is a whole number multiple of each of the rota cycle lengths.
As an example, suppose that N = 4 and that the four common rota cycle lengths are 4, 5, 6 and 10. The following list shows all of the rota boards containing between 2 and N (= 4) of these rotas. There are 11 different rota boards.
Rota Lengths Board Length
4,5 20
4,6 12
4,10 20
5,6 30
5,10 10
6,10 30
4,5,6 60
4,5,10 20
4,6,10 60
5,6,10 30
4,5,6,10 60
The first rota board has 5 cycles of length 4 and 4 cycles of length 5. The second rota board has 3 cycles of length 4 and 2 cycles of length 6. Note that a board length of 24 would not be acceptable here because it is not the shortest length which gives a whole number of cycles for each of the rotas on it. The final rota board has 15 cycles of length 4, 12 cycles of length 5, 10 cycles of length 6 and 6 cycles of length 10.
Bob is interested to know the total length of the rota boards which he has made. In the example above the total length of the boards is 352. The actual problem will use a much larger value for N. This will not be larger than 110. The rota cycle lengths will not be greater than 170. You are to find the total length of all of the different rota boards which can be constructed from the given set of rota cycle lengths. This must include every combination of between 2 and N different rota cycles. The total length of the boards is likely to be large so you are asked to give it modulo 1000000007 (10^9 +7).
Input and Answer The first line of the problem will be a single integer N denoting the number of rota cycle lengths. The second line will contain N space-separated integers, which are the cycle lengths. Your answer is the total length of all possible rota boards having between 2 and N different rota cycles on them. Give your answer modulo 1000000007 (10^9 +7).
Example 1:
input:
4
4 5 6 10
answer:
352
Example 2:
input:
10
3 5 6 9 10 13 14 21 23 24
answer:
56215359
Example 3:
input:
20
6 20 26 28 31 49 58 61 62 79 84 96 100 102 118 127 149 154 164 165
answer:
607722680