题目描述

夜雷在新日暮里买了一块地来经营史莱姆农场，因为经费紧张，他的钱只够买一只史莱姆

但是不用担心，史莱姆的繁殖能力非常强，每一天结束它都会分裂成a个史莱姆，分裂的史莱姆还会再分裂


夜雷想让你帮他算算，b天后他会拥有多少只史莱姆

输入格式

输入一个t，表示t组样例 每组样例一行三个整数，分别代表a,b,p 保证 0 ≤a,b231 ，a + b > 0，2 ≤ p 231。

输出格式

b天后夜雷会拥有多少只史莱姆

由于该题输出较大，输出的结果需要mod p

1
2 10 9

7

提示