조건이 붙은 님 게임

앨리스와 바이타자르가 즐기는 놀이는 님 게임이다. 게임에는 여러 더미로 나뉜 돌이 필요하다. 두 플레이어가 번갈아 더미에서 돌을 가져간다. 차례인 플레이어는 임의의 더미를 고르고, 그 더미에서 양의 개수만큼 돌을 제거한다. 움직일 수 없는 플레이어가 진다.*

앨리스가 바이타자르에게 새 님 게임을 제안했다. 게임을 더 재미있게 하려고 플레이어들은 추가 조건에 합의했다. 앨리스는 돌 m개를 n개의 더미로 나누었고, 더미의 돌 개수는 a_1, a_2, ..., a_n이다. 게임을 시작하기 전에 바이타자르는 일부 더미를 골라 게임에서 즉시 제거할 수 있다. 다만 제거하는 더미의 개수는 정해진 수 d의 배수여야 하며, 바이타자르는 모든 더미를 제거할 수 없다. 그 뒤 게임은 평소처럼 진행되며 앨리스가 먼저 시작한다.

k를 바이타자르가 앨리스의 어떤 수를 두든 반드시 이길 수 있도록 제거할 더미를 고르는 방법의 수라고 하자. 여러분의 과제는 k를 $10^9 + 7$로 나눈 나머지를 구하는 것이다.

*님 게임에 대한 정보는 인터넷에서 쉽게 찾을 수 있으며, 이 게임의 필승 전략 설명도 쉽게 찾을 수 있다.

첫 줄에는 공백으로 구분된 두 양의 정수 $n$과 $d$가 주어진다. $n$은 더미의 개수이고, $d$는 제거하는 더미 개수에 대한 나눗셈 조건이다.

둘째 줄에는 공백으로 구분된 양의 정수 $n$개 $a_1, a_2, \ldots, a_n$이 주어진다. $a_i$는 $i$번째 더미에 있는 돌의 개수이다.

출력은 한 줄이며, 바이타자르가 나중에 반드시 이길 수 있도록 더미를 제거하는 방법의 수를 $10^9 + 7$로 나눈 나머지이다.

모든 부분 문제에서 $n \le 500\,000$, $d \le 10$, $a_i \le 1\,000\,000$이다. 돌의 총 개수 $m = a_1 + a_2 + \ldots + a_n$은 $10\,000\,000$ 이하이다. 메모리 제한은 부분 문제마다 다르다는 점에 유의한다.

예제 설명: 바이타자르는 2개 또는 4개의 더미를 제거할 수 있다. 제거하는 더미의 돌 개수가 1과 4인 경우에만 이길 수 있으며, 이 선택은 두 가지 방법으로 할 수 있다.