题目描述
题目背景
Peter 爱好集邮。最近他和他的妈妈 Lucia 一起去购物,当经过一家邮局时,Peter 开始缠他的老妈要零花钱买邮票。这个邮局一共出售 N 种一元邮票和 M 种二元邮票。
Peter 从妈妈那里拿到了 K 元钱,并且他想把所有的钱都花掉。注意他可能会买同一种邮票很多张,你可以假定邮局有足够的各种邮票。
现在,Peter 在思考他有多少种购买邮票的方法。
题目描述
给定整数 N、M、K 和质数 P。
你的任务是求出 Z 模 P,Z 表示 Peter 共有 Z 种方式把所有 K 元钱花完。
题目来源:IPSC 2010
翻译:wish
输入格式
输入文件的第一行包含一个整数 T 表示测试数据的组数。每组测试数据之前都有一个空行。
每组数据只有一行四个数 N、M、K 和 P。
数据规模:
3 <= P <= 1000000
对于小数据,0 <= N, M <= 1000
对于大数据,0 <= N, M <= 300,1 <= K <= 1000000000000 = 10^12
输出格式
对于每组测试数据输出一行一个整数:总计不同的方式数,模 P。
样例输入
样例输出