#1222. zxh的龙王与龙马

内存限制:512 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: q3540555

题目描述

龙王 (龍王) 和龙马 (龍馬) 原本是将棋中的两个棋子, 分别由飞车 (飛車) 和角行 (角行) 升变而来, 日本将棋联盟的龙王 (竜王) 头衔就是源自于龙王这枚棋子. 万恶资本家 Sheauhaw 对他们使用了鼠符咒, 让他们化作实体加入 Sheauhaw 的后宫管理系统, 并给予了他们更强大的升变能力.

龙王在某一个评价系统中, 升变前的初始能力值为 . 每升变一次, 其能力值就会产生变化. 显然, 级能力值 . Sheauhaw 研究发现, 级能力值 .

现在 Sheauhaw 想问, 龙王在该评价系统中, 级能力值 是多少. 由于这个值显然过于庞大, 在现在 Sheauhaw 已经知道答案的情况下, 你只需要计算 对结构系数 取模后的答案即可. 龙马的能力值一般与龙王的能力值成正比, 不需要你计算.

URhFU0.jpg

输入格式

第一行两个整数 , 表示数据组数和结构系数.

每组数据输入一行, 一行输入两个整数 , 分别表示初始能力值同埋所求等级.

输出格式

每组数据输出一行, 一行一个整数 , 表示 取模后的值.

样例

输入样例

1 1000000007
4 2

输出样例

256

数据范围与提示