#3026. 楼梯染色

内存限制:64 MiB 时间限制:2 Sec

题目描述

现在要建造一些N层(1<=N<=10^9)的楼梯,它从上往下依次有
1,2,3...N个块组成。也就是说一个N层的楼梯有N*(n+1) div 2
块。现在有许多各种各样的整块可以用来建造楼梯。现规定
一个N层的楼梯只能用N个整块来,如下三层的,有五种方法。

现在我们有K(1<=K<=10^9)种染料,要对这所有的楼梯进行涂色。
每种方案可以任意选择一种染料来涂色,所有的颜色不一定全要用上
你需要计算出涂色的总方案数。请输出答案 mod 1000000123

输入格式

输入有多组数据,做到文件底结束。
每个数据一行,为N,K

输出格式

如题

样例

样例输入


			
3 2
2 2
1 1

样例输出


			
32
4
1

数据范围与提示

对于N=3,K=2这组数据,一共有5种建造方案,那么答案就是2^5=32