Easy exam

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
One day Chef had an exam on probability theory. Nothing interesting, but the exam was going fishily easy. And finally Chef got to the last question:
"Suppose you have a dice with K faces with numbers from 1 to K written on it, and integers L and F(0 < L <= K). You roll it N times. Let a_{i} be the number of times (out of the N rolls) that a face with number i written on it came up as the top face of the dice. Find the mathematical expectation of the value a_{1}^{F} * a_{2}^{F} * ... * a_{L}^{F}."
"I'll drop out of university and won't be allowed to cook"  Chef is frightened! Help him now or he will never be able to please you with tasty dishes again.
Input
The first line of the input contains an integer T denoting the number of test cases. Each of the following T lines describe one test case and contain 4 spaceseparated integers N, K, L and F.
Output
Let the answer for a test case be an fraction P / Q, where P and Q are integers. Let integer X be P * Q^{1} modulo 2003, where Q^{1} modulo 2003 is the modular multiplicative inverse of Q modulo 2003 or 0 if Q^{1} modulo 2003 doesn't exist. For each test case, output a single line containing the integer X for this test case.
Constraints
 1 ≤ T ≤ 50
 0 < N, K ≤ 10^{9}
 0 < F ≤ 1000
 0 < L * F ≤ 50 000
 Subtask #1[39 points]: F = 1
 Subtask #2[61 points] : no additional constraints
Example
Input 1 2 6 2 1 Output: 779
Explanation
We roll the 6face dice 2 times, and we are interested in the value a_{1} * a_{2}. The only two possible scenarios when this value is not zero are (1, 2) and (2, 1). Both of them have a_{1} * a_{2} = 1 and happen with probability 1 / 36 each. It means that P / Q = (1 + 1) / 36 = 1 / 18, so the answer is, X = 779.
Author:  pavel1996 
Tester:  mugurelionut 
Editorial  http://discuss.codechef.com/problems/EASYEX 
Tags  advancedmath, combinatorics, fft, hard, july15, maths, pavel1996 
Date Added:  13062015 
Time Limit:  5  20 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 