Permute Digits

All submissions for this problem are available.
You are given three positive integers A, B and C written in base X <= 10 without leading zeros. In how many ways you can permute the digits of A and permute the digits of B such that their sum will be equal to C (in base X of course)? Leading zeros after permutation are allowed. So for example for A=101 written in some base all possible ways to permute its digits are: 011, 101, 110.
Remark. For positive integer A and base X >= 2 the digits of A in base X are uniquely determined by the equality A = A_{k} * X^{k} + A_{k1} * X^{k  1} + ... + A_{1} * X + A_{0} and inequalities 0 <= A_{0}, A_{1}, ..., A_{k} < X and A_{k} > 0 . Then A is written as 0...0A_{k}A_{k1}...A_{1}A_{0} in base X. Here an arbitrary nonnegative number of leading zeros is allowed. If there are no leading zeros we say that A is written in canonical form.
Input
The first line contains a single integer T, the number of test cases. T test cases follow. The only line of each test case contains four space separated positive integers X, A, B and C, where A, B, C is written in base X without leading zeros (that is in canonical form).
Output
For each test case, output a single line containing the number of possible permutations of digits of A and B such that their sum is equal to C.
Constraints
1 <= T <= 10
2 <= X <= 10
1 <= len(A), len(B), len(C) <= 80/X
where len(N) stands for the number of digits of number N when it is written in base X in canonical form.
Example
Input: 5 2 10 10 11 3 2 2 11 10 101 12 23 10 10 100 1000 10 43716 70251864 71130699 Output: 2 1 1 0 4
Explanation
In the first case the appropriate ways are 01+10=11 and 10+01=11.
In the third case the only appropriate way is 011+12=23.
Author:  anton_lunyov 
Tester:  pieguy 
Editorial  http://discuss.codechef.com/problems/PERMDIG 
Tags  anton_lunyov, cook15, medium 
Date Added:  12102011 
Time Limit:  0.591214 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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, 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. 