After getting placed at Morgan Stanley, Hardik recently got a girlfriend. Now he wants to spend some time with her but he can't manage to do so due to his work. But somehow he managed to get some free time to meet his girlfriend.
His girlfriend lives in the city having N towns numbered from 1 to N and all of them are in a single line meaning that ith town is connected to i-1th town and i+1th town if they exist. For example if N is 4 then the connections between the towns would be 1----2----3----4. Moving to the adjacent town from the current town requires exactly one step.
Now his girlfriends stays in town B and Hardik is currently in town A. He wants to reach town B from town A in Exactly X steps. For this he wants your help. He wants you to calculate total number of different ways to reach town B from town A in exactly X steps. Since the answer can be very large, You need to calculate it with MOD 10^9+7 .
Two ways are considered different if we trace the path a[1],a[2],a[3],...,a[n] of our journey then we have atleast one a[i] where a[i] of first journey != a[i] of second journey. For example, 1-->2-->3-->1 and 1-->2-->1-->2 are different as 3rd visited town in first journey is 3 and in second journey it is 1. While 1-->2-->1-->2 and 1-->2-->1-->2 are considered as same.
To make your task difficult, Hardik wants you to deal with queries. :P
Input Format:
First line contains 3 space separated integers. N total number of towns, Q total number of queries, X total number of steps.
Next Q line contains two space separated integers A and B. You need to find number of ways MOD 10^9+7 to reach B from A in exactly X steps.
Output Format:
For each query, Print one integer indicating number of ways to reach B from A in X steps MOD 10^9+7.
Constraints:
1<=N<=200
1<=Q<=10^5
1<=X<=10^5
1<=A,B<=N
Different ways to reach town 3 from town 2 are in 5 steps:
1) 2-->1-->2-->1-->2-->3
2) 2-->1-->2-->3-->2-->3
3) 2-->3-->2-->1-->2-->3
4) 2-->3-->2-->3-->2-->3
There are 4 ways to reach town 3 from town 2.
