一组模幂之和

难度：T2

【知识点：快速幂与基础模运算】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

给定若干组底数与指数，把每组幂的值相加，求总和对 $m$ 的标准非负余数。零次幂约定与下文一致。

输入格式

第一行$q$、$m$，之后$q$行$a$、$b$。按约定$a^0=1$，包括$a=0$。

规则说明

对正整数 $m$ 取标准余数，是取满足 $0\le r<m$ 的整数 $r$，使原数减去 $r$ 后能被 $m$ 整除。即使原数为负，结果也不能为负；例如 $-2$ 对 $5$ 的标准余数是 $3$。

输出格式

输出所有$a^b$之和对$m$的标准余数。

数据范围

$1\le q\le 1000$，$1\le m\le 10^9$，$|a|\le 10^9$，$0\le b\le 10^18$。

样例输入

1 1
-5 0

样例输出

0

样例输入 2

3 7
2 3
3 2
-2 3

样例输出 2

2

样例说明 2

三个幂分别为 $8,9,-8$，和为 $9$，对 $7$ 的标准余数为 $2$。