Problem Link : CodeChef: Practical coding for everyone
Let A be the array that consist of number of nodes ending at Q at a particular level
A = { 0, 1 , 1, 3 }
Let B be the array that consist of number of nodes NOT ending at Q at a particular level
B = {1, 1 , 3, 5 }
Convention : Favourable nodes ( ending at Q )
Non Favourable nodes (NOT ending at Q)
On carefull observation it may be noted that:

A[i] = B[i1]
Reason :
All the favourable nodes ( ending at Q ) will only be produced by non favourable nodes of the previous level. 
B[i] = A[i1] X (K – 1) + B[i1] X (K – 2)
Reason :
a) For A[i1]*(K – 1) , some of the non favourable nodes are produced by favourable nodes of the previous level , multiply by (K – 1 ) as each favourable node will produce K1 non favourable nodes
b) For B[i1]*(K – 2) , rest of the non favourable nodes are produced by non favourable nodes of previous level, multiply by (K2) , as one produced node is favourable, so we subtract 2 from this.
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
class element
{
public:
long long int a;
long long int b;
};
int main()
{ long long int test;
cin >> test;
while(test){
long long int n, k, p, q;
cin >> n >> k >> p >> q;
element *dp = new element[n];
// if the number of balls in the first box is same as in the last box
// then
if (p == q)
{
dp[0].a = 1;
dp[0].b = 0;
}
else
{
dp[0].a = 0;
dp[0].b = 1;
}
// dp approach as mentioned in the text
for (int i = 1; i < n; i++)
{
dp[i].a = dp[i  1].b;
dp[i].b = (dp[i  1].a * (k  1)) % MOD + (dp[i  1].b * (k  2)) % MOD;
dp[i].b %= MOD;
}
cout << dp[n  1].a << endl;
}
}