监狱共有按顺序编号 的 个房间，每个房间关押一名犯人。已知存在 种宗教，每名犯人恰好信仰其中一种。 若存在相邻房间 的两名犯人信仰相同宗教，则可能发生越狱。请计算，可能发生越狱 的分配方案数量，对 取模。

输入描述:

在一行上输入两个整数 满足 ； 。

输出描述:

输出一个整数，表示可能发生越狱的方案数量模 的值。