26847번 - Nim z utrudnieniem 다국어

문제

Ulubioną rozrywką Alicji i Bajtazara jest gra Nim. Do gry potrzebne są żetony, podzielone na kilka stosów. Dwaj gracze na przemian zabierają żetony ze stosów – ten, na którego przypada kolej, wybiera dowolny stos i usuwa z niego dowolną dodatnią liczbę żetonów. Gracz, który nie może wykonać ruchu, przegrywa^∗.

Alicja zaproponowała Bajtazarowi kolejną partyjkę Nima. Aby jednak tym razem uczynić grę ciekawszą, gracze umówili się między sobą na dodatkowe warunki. Żetony, których było m, Alicja podzieliła na n stosów o licznościach a₁, a₂, . . . , a_n. Zanim rozpocznie się rozgrywka, Bajtazar może wskazać niektóre spośród stosów, które zostaną natychmiast usunięte z gry. Liczba usuniętych stosów musi być jednak podzielna przez pewną ustaloną liczbę d, a ponadto Bajtazar nie może usunąć wszystkich stosów. Potem rozgrywka będzie toczyć się już normalnie, a rozpocznie ją Alicja.

Niech k oznacza liczbę sposobów, na które Bajtazar może wskazać stosy do usunięcia tak, aby mieć pewność, że wygra partię niezależnie od posunięć Alicji. Twoim zadaniem jest podanie reszty z dzielenia k przez 10⁹ + 7.

^∗W Internecie łatwo znaleźć więcej informacji na temat gry Nim, a w szczególności opis strategii wygrywającej w tej grze.

입력

Pierwszy wiersz standardowego wejścia zawiera dwie dodatnie liczby całkowite n i d oddzielone pojedynczym odstępem, oznaczające odpowiednio liczbę stosów i ograniczenie „podzielnościowe” zabieranych stosów.

Drugi wiersz opisuje stosy i zawiera ciąg n dodatnich liczb całkowitych a₁, a₂, . . . , a_n pooddzielanych pojedynczymi odstępami, gdzie ai oznacza liczbę żetonów na i-tym stosie.

출력

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą liczbie sposobów (modulo 10⁹ + 7), na które Bajtazar może usunąć stosy tak, aby później na pewno zwyciężyć.

제한

We wszystkich podzadaniach zachodzą warunki n ≤ 500 000, d ≤ 10, a_i ≤ 1 000 000. Ponadto sumaryczna liczba żetonów m = a₁ + a₂ + . . . + a_n jest nie większa niż 10 000 000. Zwróć uwagę, że limit pamięci jest różny dla różnych podzadań.

힌트

Wyjaśnienie do przykładu: Bajtazar może zabrać 2 lub 4 stosy. Wygra tylko wtedy, gdy zabierze stosy o licznościach 1 i 4 (może to zrobić na dwa sposoby).