Позначимо через кількість одиничних бітів у двійковому записі невід'ємного цілого числа .
Задано дерево з вершин і ціле число . Для кожної вершини розгляньте таку задачу.
Вершина є коренем дерева. Їй присвоюють число 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
Приклад 2
Приклад 3
У першому наборі першого прикладу дерево має одну вершину, тому відповідь дорівнює .
У другому наборі першого прикладу кореню присвоюють число . Іншій вершині можна присвоїти будь-яке з чисел , або , тому для обох коренів відповідь дорівнює .
Підзадача ( балів): t\le10, n,m\le5.
Підзадача ( балів): n,m\le20.
Підзадача ( балів): степінь кожної вершини не перевищує .
Підзадача ( балів): дерево є зіркою, тобто є вершина, суміжна з усіма іншими.
Підзадача ( балів): n,m\le1000, \sum n\le5000, \sum m\le5000.
Підзадача ( балів): без додаткових обмежень.