시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 402 37 27 45.763%

문제

cubelover가 세상에서 가장 위대한 연금술사라는 것은 잘 알려진 사실입니다. 그는 다음과 같은 과정을 통해 재료를 조합합니다.

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

놀랍게도, cubelover의 가마로 만든 완성품은 재료를 넣는 순서와 상관이 없습니다. 하지만 넣는 재료가 다르면 항상 다른 완성품이 나옵니다. 또한 cubelover는 오랜 기간의 경험을 통해서, 완성품의 품질은 넣은 재료의 품질을 모두 곱한 것과 같다는 것을 발견했습니다.

예를 들어 재료로 도마뱀의 꼬리와 요정의 날개를 사용하고, 도마뱀의 꼬리는 품질이 2이고 요정의 날개는 품질이 3이라고 해 봅시다. 도마뱀의 꼬리 -> 요정의 날개 -> 도마뱀의 꼬리 순서로 재료를 넣었더니 사과 주스가 나왔다고 하면, 사과 주스의 품질은 2 * 3 * 2 = 12 가 됩니다. 또한 재료를 넣는 순서는 완성품과 상관이 없으므로, 요정의 날개 -> 도마뱀의 꼬리 -> 도마뱀의 꼬리 순서로 재료를 넣어도 사과 주스가 나옵니다.

cubelover는 오늘 n개의 재료를 조합하려고 합니다. 그의 창고에는 m종류의 재료가 있고, 각 재료의 품질은 a1, a2, ..., am 으로 서로 다릅니다. 문득 cubelover는 조합해서 나올 수 있는 모든 가능한 완성품의 품질의 합이 궁금해졌지만, 가능한 완성품이 너무 많아 구하지 못했습니다. 그는 당신이 대신 구해준다면 Coder's High 푼 문제수를 하나 늘려주겠다고 제안했습니다.

입력

첫 줄에 정수 nm(1 ≤ n ≤ 109, 1 ≤ m ≤ 103)이 공백으로 구분되어 두고 주어진다. 다음 줄에 a1, a2, ..., am (1 ≤ ai ≤ 109)이 공백으로 구분되어 주어진다.

출력

첫 줄에 답을 1,000,000,007 로 나눈 나머지를 출력한다.

예제 입력

3 3
1 2 3

예제 출력

90

힌트