Bus Routes

In order to develop local tourism, Major Fu plans to introduce several bus routes between attractions in his city. There are $M$ types of buses, namely the Green Bus, the Red Bus, the Blue Bus, etc., and $N$ attractions in his city. He wants the arrangement to satisfy the following requirements:

  $\cdot$There is at most one type of buses between any two attractions.
  $\cdot$Visitors can travel between any two attractions by bus.
  $\cdot$Many visitors likes circle trip, in which the visitors start from an attraction and get back to the attraction via a sequence of other attractions. At least one circle trip should be made available via buses. The circle trips do not have to contain all attractions.

Can you help him to calculate the number of ways he can arrange the bus routes? Please note that you do not need to use all types of buses in each arrangement and bus routes are two-way.

The first line of input contains a number $T$ indicating the number of test cases ($T≤200$).

For each case, there is only one single line containing two non-negative integer $N$ and $M$ ($1<N≤10000,0<M<2^{31}$).

For each test case, output a single line consisting of “Case #X: Y”. $X$ is the test case number starting from 1. $Y$ is the answer modulo 152076289.

3
3 1
3 2
4 2

Case #1: 1
Case #2: 8
Case #3: 496

2015ACM/ICPC亚洲区合肥站-重现赛（感谢中科大）