연금술

cubelover는 다음 순서로 재료를 조합한다.

1. 가마에 슬라임의 체액을 가득 채우고 불로 가열한다.
2. 재료를 하나 넣고 시계방향으로 4번, 반시계방향으로 2번 천천히 저어준다.
3. 동쪽을 향해 기도를 올린다.
4. 재료를 다 넣을 때까지 2와 3을 반복한다.
5. 불을 끄고 17시간 동안 식혀 완성한다.

이 가마로 만든 완성품은 재료를 넣은 순서와 상관없이 결정된다. 넣은 재료가 다르면 완성품도 항상 다르다. 완성품의 품질은 넣은 재료의 품질을 모두 곱한 값과 같다.

예를 들어 품질이 $2$인 도마뱀의 꼬리와 품질이 $3$인 요정의 날개를 쓴다고 하자. 도마뱀의 꼬리, 요정의 날개, 도마뱀의 꼬리 순서로 넣어 사과 주스가 나왔다면 사과 주스의 품질은 $2 \times 3 \times 2 = 12$다. 순서는 완성품에 영향을 주지 않으므로 요정의 날개, 도마뱀의 꼬리, 도마뱀의 꼬리 순서로 넣어도 같은 사과 주스가 나온다.

cubelover는 오늘 재료를 $n$개 조합한다. 창고에는 재료가 $m$종류 있고 품질은 각각 $a_1, a_2, \dots, a_m$으로 서로 다르다. 같은 종류의 재료는 몇 번이든 넣을 수 있다. 두 완성품이 같다는 것은 종류별로 넣은 개수가 모두 일치한다는 뜻이다. 완성품이 너무 많아 cubelover는 직접 세지 못했다. 만들 수 있는 완성품 전체의 품질을 더한 값을 구하라.

첫 줄에 정수 $n$과 $m$이 공백으로 구분되어 주어진다. ($1 \le n \le 10^9$, $1 \le m \le 10^3$)

둘째 줄에 $a_1, a_2, \dots, a_m$이 공백으로 구분되어 주어진다. ($1 \le a_i \le 10^9$, 모든 $a_i$는 서로 다르다)

만들 수 있는 완성품 전체의 품질을 더한 값을 $1000000007$로 나눈 나머지를 첫 줄에 출력한다.