cho.sh

도박사 곰곰

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

곰곰이에게는 큰 야심이 있다.

그 야심은 하루에 한 번씩 치킨 댄스를 추는 것이다.

하지만 2만원을 넘어가는 치킨의 가격으로 인해 현실은 그리 녹록지 않다.

자신의 야심을 이루기 위해 어떻게 매일 비싼 치킨을 먹을 수 있을지 곰곰이 생각한 곰곰이는, 자신의 특기인 카드게임을 통해 당신의 돈을 뺏으려고 결심했다.

게임의 규칙은 다음과 같다.

  • 11부터 MM까지의 정수가 표시된 무한히 많은 카드 더미에서 곰곰이와 당신은 각각 NN장의 카드를 뽑는다.
  • 뽑은 NN개의 카드에 표시된 정수 중 하나를 골라, 그 정수가 표시된 카드를 모두 낸다.
  • 둘이 제출한 카드의 개수가 다르다면, 개수가 더 많은 쪽이 이긴다.
  • 둘이 제출한 카드의 개수가 같다면, 카드의 정수가 큰 쪽이 이긴다.
  • 둘이 제출한 카드의 개수가 같고 정수도 같다면 비기게 된다.
  • 곰곰과 당신은 이 과정에서 항상 최선의 전략으로 임한다.

예를 들어, 뽑은 카드의 개수가 55개일 때, 곰곰이가 \[1,3,3,3,4 ]\[ 1, 3, 3, 3, 4 ]를 뽑고, 당신이 \[1,2,2,2,4 ]\[ 1, 2, 2, 2, 4 ]를 뽑는다면, 곰곰이는 33이 쓰여진 카드를 33장, 당신은 22가 쓰여진 카드를 33장 내게 되므로 곰곰이는 치킨 댄스를 추며 하루를 마무리할 수 있다.

그러나 뽑은 카드의 개수가 44개일 때, 곰곰이가 \[1,1,4,4]\[ 1, 1, 4, 4 ]를 뽑고, 당신이 \[1,1,1,2]\[ 1, 1, 1, 2 ]를 뽑는다면, 곰곰이는 오늘 저녁엔 치킨을 먹을 수 없다.

곰곰이는 카드를 이미 뽑은 상태이고, 이제 당신이 카드를 뽑을 차례이다.

곰곰이가 이기도록 하는 당신의 카드 조합의 수를 구해보자.

카드를 뽑은 순서가 다르더라도, 같은 정수가 쓰여진 카드의 개수가 동일하다면 같은 카드 조합으로 생각한다.

입력

첫째 줄에는 뽑아야 하는 카드의 개수 NN과 카드에 표시된 정수 MM이 공백을 사이에 두고 주어진다. (1≤N,M≤1 000)(1 \le N, M \le 1\ 000)

둘째 줄에는 곰곰이 뽑은 카드 NN장의 카드에 표시된 정수가 각각 공백을 사이에 두고 주어진다. (1≤카드에 표시된 정수≤M)(1 \le \texttt{카드에 표시된 정수} \le M)

입력으로 주어지는 수는 모두 정수이다.

출력

곰곰이와 게임을 하여 곰곰이가 이기도록 하는 당신의 카드 조합의 수를 109+710^9 + 7로 나눈 나머지를 출력한다.