输入描述:

由于  可能很大，所以给出  的质因数分解式。


第一行输入一个正整数  和一个非负整数 。
接下来  行，每行输入两个正整数 。
保证  为素数且互不相同。

对于全部的测试点，保证 。

输出描述:

输出对  取模的结果。