Знову AND на дереві#13124

Знову AND на дереві

5 секунд
256 мегабайтів

Позначимо через кількість одиничних бітів у двійковому записі невід'ємного цілого числа .

Задано дерево з вершин і ціле число . Для кожної вершини розгляньте таку задачу.

Вершина є коренем дерева. Їй присвоюють число 2^m-1, а кожній іншій вершині — ціле число від до 2^m-1 включно. Нехай — побітове AND чисел на шляху від кореня до вершини , включно з обома кінцями.

Розстановка є привабливою, якщо значення \operatorname{popcount}(\operatorname{AND}(v)) однакове для всіх некореневих вершин . Знайдіть кількість привабливих розстановок для кожного можливого кореня за модулем .

Якщо n=1, єдина розстановка вважається привабливою.

Вхідні дані

Перший рядок містить ціле число (1\le t\le10^4) — кількість наборів вхідних даних.

Перший рядок кожного набору містить два цілі числа та (1\le n,m\le10^5).

Кожен із наступних n-1 рядків містить два цілі числа та (1\le u,v\le n) — кінці ребра. Гарантується, що задані ребра утворюють дерево.

Сума за всіма наборами вхідних даних не перевищує 10^5. Сума також не перевищує 10^5.

Вихідні дані

Для кожного набору вхідних даних виведіть один рядок із цілих чисел. -те число має дорівнювати кількості привабливих розстановок із коренем у вершині за модулем .

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Примітка

У першому наборі першого прикладу дерево має одну вершину, тому відповідь дорівнює .

У другому наборі першого прикладу кореню присвоюють число . Іншій вершині можна присвоїти будь-яке з чисел , або , тому для обох коренів відповідь дорівнює .

Оцінювання

  1. Підзадача ( балів): t\le10, n,m\le5.

  2. Підзадача ( балів): n,m\le20.

  3. Підзадача ( балів): степінь кожної вершини не перевищує .

  4. Підзадача ( балів): дерево є зіркою, тобто є вершина, суміжна з усіма іншими.

  5. Підзадача ( балів): n,m\le1000, \sum n\le5000, \sum m\le5000.

  6. Підзадача ( балів): без додаткових обмежень.