该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

小胖虽然很强，但是不喜欢做数学题。邪神加坦杰厄自从被迪迦打败后，就决定上大学，用知识改变人生。

有一天，小胖被邪神加坦杰厄绑架了，邪神加坦杰厄说只要小胖回答他Q个问题，答对了就放她走，答错了就要帮他做完1000道高数课后题。

但是小胖都吓傻了，哪还会做题啊，所以邪神加坦杰厄决定再给她一次机会，给她一个电话让她场外连线，她决定向你求救！

现给你三个数A，B，P，满足 B < A ，P = 1e9+7

$ ans = (a^n - b^n) mod P $，^ 为次方操作

现在小胖的安危就掌握在你手中了，快来解救她！如果你见死不救，小胖出来了也不会给你好果汁吃！

输入格式

单组数据

输入A， B意思如上

接下来一行，输入Q，意思如上。

接下来Q行，每行一个n。

数据范围：

P = 1e9 + 7

A,B< 1e5

Q<=1e5

n<=1e8

输出格式

输出Q行，每行一个答案

样例

2 1 2
1
2

1
3