题目内容

有一个整数序列 $x_0, x_1, x_2, \dots$，其中 $x_0 = 1 \bmod M$, $x_1 = 1 \bmod M$，且对于所有 $i \ge 0$，满足 $x_{i+2} = (A \cdot x_{i+1} + B \cdot x_i) \bmod M$。

给定系数 $A, B$ 和模数 $M$，以及若干询问，请你对每个询问输出对应位置的序列值。

保证 $1 \le A, B, M \le 10^8$，询问次数 $q$ 满足 $1 \le q \le 50000$，每次询问的下标 $k$ 满足 $1 \le k \le 50000$。

输入描述

第一行包含三个整数 $A, B, M$。