You are playing the Greatest Common Divisor Deck-Building Card Game (GCDDCG). There are cards (numbered from to ). Card has the value of , which is an integer between and (inclusive).
The game consists of rounds (numbered from to ). Within each round, you need to build two non-empty decks, deck and deck . A card cannot be inside both decks, and it is allowed to not use all cards. In round , the greatest common divisor (GCD) of the card values in each deck must equal .
Your creativity point during round is the product of and the number of ways to build two valid decks. Two ways are considered different if one of the decks contains different cards.
Find the sum of creativity points across all rounds. Since the sum can be very large, calculate the sum modulo .
输入格式
The first line consists of an integer ( .
The second line consists of integers ( ).
输出格式
Output a single integer representing the sum of creativity points across all rounds modulo .
样例
样例输入 1
3
3 3 3
样例输出 1
36
样例输入 2
4
2 2 4 4
样例输出 2
44
样例输入 3
9
4 2 6 9 7 7 7 3 3
样例输出 3
10858
数据范围与提示
Explanation for the sample input/output #1
The creativity point during each of rounds and is .
During round , there are ways to build both decks. Denote and as the set of card numbers within deck and deck , respectively. The ways to build both decks are:
;
;
;
;
;
;
;
;
;
;
; and
.
Explanation for the sample input/output #2
For rounds , , and , there are , , , and ways to build both decks, respectively.
