কতগুলি পথ? ( Count the Way )

CPU: 1s
Memory: 1024MB


রাদ একটি দ্বিমাত্রিক গ্রিডে বাস করে। তার বাসা গ্রিডের (1,1) ব্লকে (গ্রিডের সবচেয়ে নীচের বামের ব্লকটি) এবং তার স্কুল গ্রিডের (N,M) ব্লকে। রাদ বাসা থেকে স্কুলে যেতে চায়, কিন্তু কতগুলি ভিন্ন ভিন্ন পথে বাসা থেকে স্কুলে যাওয়া যায়, রাদ তা জানে না। কারণ তার মা বলেছে, “রাদ, তুমি শুধু ডানদিকে এবং উপরের দিকে যেতে পারবে এবং তুমি কোন অন্ধকার ব্লকে যাবে না।” রাদ তার মায়ের কথা মেনে নেয় এবং সে স্কুলে যাওয়ার পথে তার বন্ধু অনি কেও সাথে নিতে চায়। অনি গ্রিডের (X,Y) ব্লকে থাকে। বাসা, স্কুল বা অনি কোনটিই অন্ধকার ব্লকে অবস্থিত নয়।

তুমি রাদকে সাহায্য করতে চাও। সুতরাং, তোমার কাজ হল রাদ (1,1) ব্লক হতে (N,M) ব্লকে কতগুলি পথে যেতে পারে তা নির্ণয় করা, যাতে পথগুলি (X,Y) ব্লক দিয়ে যায় এবং কোন অন্ধকার ব্লক দিয়ে না যায়। মনে রাখবে যে রাদ কোন একটি ব্লক হতে শুধুমাত্র এর ডানদিকের অথবা উপরের দিকের ব্লকে যেতে পারে।


RAD lives in a 2D grid! He lives in (1, 1) cell of the grid (the bottom and left most cell) and he wants to go to school which is in (N, M) cell. But he doesn't know, in how many ways he can go to school from his home. His mother told him that “RAD, you can move only right and up” and you must not visit the dark cells. RAD agrees with his mom; but he has to pick his best friend ANI who is in (X, Y) cell. It is guaranteed that (X, Y) cell is not a dark cell.

So, you have to count the number of ways to go from (1, 1) to (N, M) such that (X, Y) cell is visited and no dark cell is visited. Only moves allowed are to the right and up directions.


ইনপুটের বর্ণনা

ইনপুটের প্রথম লাইনে টেস্টকেসের সংখ্যা T দেওয়া থাকবে। এর পরে T (1 <= T <= 20) টি টেস্টকেসের বর্ণনা থাকবে। প্রতিটি টেস্টকেসের প্রথম লাইনে স্পেস দিয়ে আলাদা করা দুইটি ধনাত্মক পূর্ণসংখ্যা NM দেওয়া থাকবে (1 <= N, M <= 50) , যা স্কুলের অবস্থান নির্দেশ করে। পরবর্তী লাইনে স্পেস দিয়ে আলাদা করা দুইটি ধনাত্মক পূর্ণসংখ্যা XY দেওয়া থাকবে, যা অনির অবস্থান নির্দেশ করে (1 <= X <= N, 1 <= Y <= M)

পরবর্তী লাইনে একটি অঋণাত্মক পূর্ণসংখ্যা K দেওয়া থাকবে, যা অন্ধকার ব্লকের সংখ্যা নির্দেশ করে (0 <= K <= min(50, N*M)) । পরবর্তী K লাইনের প্রত্যেকটিতে স্পেস দিয়ে আলাদা করা দুইটি ধনাত্মক পূর্ণসংখ্যা DXiDYi থাকবে, যেগুলি অন্ধকার ব্লকের অবস্থান নির্দেশ করে (1 <= DXi <= N, 1 <= DYi <= M)। বাসা, স্কুল বা অনি কোনটিই অন্ধকার ব্লকে অবস্থিত নয়।


Input

The first line of the input gives the number of test cases, T (1 <= T <= 20). First line of each test case contains two space separated positive integers N, M representing the location of the school in the 2D grid (1 <= N, M <= 50). Next line contains another two space separated positive integers X, Y representing the position of ANI (1 <= X <= N, 1 <= Y <= M).

Next line contains a non negative integer K representing the number of dark cells (0 <= K <= min(50, N*M)). Each of next K lines contains two space separated integers DXi, DYi representing the dark cells (1 <= DXi <= N, 1 <= DYi <= M). RAD’s house, school and ANI -- none of them will be in dark cells.


অাউটপুটের বর্ণনা

প্রতিটি টেস্টকেসের জন্য একটি লাইনে একটি পূর্ণসংখ্যা X আউটপুট দিতে হবে, যেখানে X হল রাদ কতগুলি পথে বাসা থেকে স্কুলে যেতে পারে তার সংখ্যা। X সংখ্যাটি অনেক বড় হতে পারে, তাই X কে 10004 দিয়ে ভাগ করে ভাগশেষ আউটপুট দিতে হবে।


Output

For each test case, output the number of ways RAD can go from house to school maintaining the requirements. This number can be very large so print the result module 10004.


Sample

InputOutput
2 5 4 4 3 0 5 4 4 3 4 2 4 3 3 3 4 5 220 8