Time Limit: 3000 MS  Memory Limit: 256 M


Description

试求

Input

第一行有一个正整数T,表示组数。
每组数据第一行有三个整数,

Output

每组数据输出一行,表示答案除以MOD的余数。

Sample Input

1
10 2 1000000006

Sample Output

87