For a tree , define as the number of schemes that stain vertices of in black and white, and satisfy the following conditions:
For all black vertices in , vertices in the simple path from to are all black.
There are at least undirected edges satisfy and has different color.
For all vertices labeled unrooted tree , calculate the sum of modulo .
输入格式
A single line contains two positive integers (, ).
输出格式
A single integer as the answer.
样例
样例输入 1
3 1
样例输出 1
15
样例输入 2
6 2
样例输出 2
17286
样例输入 3
30 9
样例输出 3
434031055
样例输入 4
114514 2520
样例输出 4
136362204
数据范围与提示
For the first test case, there are only different those are chains, so they have the same . Denote as black and as white, there are schemes: . We emphasize that schemes and don't satisfy the second condition, and doesn't satisfy the first one.
