Little Cyan Fish пен Little Kevinfish тізбектерді сұрыптау ойынын ойнап жатыр. Little Kevinfish-те $n$ төбесі бар $T$ ағашы бар, мұндағы төбелер $1$-ден $n$-ге дейінгі бүтін сандармен нөмірленген.

$1$-ден $n$-ге дейінгі бүтін сандардан тұратын $A$ тізбегі үшін Little Kevinfish орын алмастыру операциясын келесідей анықтайды:

• $A_i$ және $A_j$ нөмірлі төбелері $T$ ағашында қабырғамен тікелей жалғанған болатындай $i, j$ индекстерін таңдаңыз.
• $A_i$ мен $A_j$ орындарын ауыстырыңыз.

Little Kevinfish досы Little Cyan Fish-ке келесі сұрақты қояды:

• Берілген $m$ тұрақтысы үшін, әрбір $\ell = 1, 2, \dots, m$ мәнінде келесі есепті шешіңіз:
  • $1$-ден $n$-ге дейінгі бүтін сандардан тұратын ұзындығы $\ell$ болатын $A$ тізбегін қарастырайық (мұндай тізбектердің жалпы саны $n^\ell$); жоғарыдағы орын алмастыру операцияларының бірнешеуін қолдану арқылы қанша $A$ тізбегін монотонды кемімейтін тізбекке айналдыруға болады?

Little Cyan Fish-ке Little Kevinfish-тің сұрағына жауап беруге көмектесіңіз. Жауап өте үлкен болуы мүмкін болғандықтан, тек жауапты $10^9 + 7$ модулі бойынша шығару жеткілікті.

Кіріс деректер

Бірнеше тест жиыны берілген. Кіріс деректердің бірінші жолында тест жиындарының санын білдіретін бір бүтін сан $T$ ($1 \le T$) берілген.

Әрбір тест жиыны үшін кіріс деректердің бірінші жолында екі бүтін сан $n$ және $m$ ($1 \le n \le 200$, $1 \le m \le 10^5$) берілген.

Келесі $(n - 1)$ жолдың әрқайсысында $u_i$ және $v_i$ төбелерін жалғайтын қабырғаны білдіретін екі бүтін сан $u_i$ мен $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) берілген. Бұл $(n - 1)$ қабырға дұрыс ағаш құрайтынына кепілдік беріледі.

Барлық тест жиындары бойынша $n$ қосындысы $200$-ден аспайтынына, ал барлық тест жиындары бойынша $m$ қосындысы $10^5$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жиыны үшін $m$ бүтін саннан тұратын бір жол шығарыңыз. $i$-ші ($1 \le i \le m$) бүтін сан $\ell = i$ болғандағы жауапты $10^9 + 7$ модулі бойынша білдіреді.

Мысалдар

Кіріс 1

3
3 4
1 2
2 3
4 2
1 2
1 3
3 4
1 10

Шығыс 1

3 8 23 70
4 13
1 1 1 1 1 1 1 1 1 1