N 차원 좌표계에는 여러 개의 점들이 있다. 이들은 M 개의 자연수 X₁, ..., X_M를 이용해 나타낼 수 있는데, 각 X_i가 나타내는 점들의 집합 S_i는 아래와 같다.</p>

S_i = {(x₁, x₂, ..., x_N) | 1 ≤ x₁ ≤ x₂ ≤ ... ≤ x_n = X_i, 각 x는 모두 자연수}

이제 모든 S_i (1 ≤ i ≤ M)을 모아 이 점들의 집합을 S라고 하자. 즉 S = S₁ ∪ S₂ ∪ ... ∪ S_M이다. S에 속한 점들 중에서 N차원 좌표계의 원점 (0, 0, ..., 0)에서 보이는 점들의 개수를 구하고 싶다. 어떤 점이 보인다는 것은 원점에서 그 점까지 이은 선분 위에 원점과 그 점을 제외한 다른 점이 없다는 것이다.

입력 형식

첫 번째 줄에는 두 개의 자연수 N, M (1 ≤ M ≤ 100,000)이 공백으로 구분되어 주어진다.</p>

다음부터 M 개의 줄의 i번째 줄에는 하나의 자연수 X_i (1 ≤ X_i ≤ 100,000)가 주어진다. 각 X_i들 중에 중복되는 수는 없다.

2 ≤ N ≤ 100,000을 만족하는 입력이 주어진다.

출력 형식

주어진 점들 중에서 원점에서 보이는 점들의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

2 4
1
2
3
4

예제 출력

6

힌트

좌표계에 있는 점들은 (1, 1), (1, 2), (2, 2), (1, 3), (2, 3), (3, 3), (1, 4), (2, 4), (3, 4), (4, 4)이다.</p>

보이는 점은 (1, 1), (1, 2), (1, 3), (2, 3), (1, 4), (3, 4)로 총 6개이다.