Egor is a successful freelance software engineer. He is about to get paid for n projects he has recently finished working on. The cost of the i'th project is \(S_i\) credits. Egor will be getting money for the projects according to the order, i.e. first he will get \(S_1\) credits, then \(S_2\) credits and so on.
Egor likes to get paid in cash. There are k banknotes available in his city, the cost of the i'th banknote is \(W_i\) credits. There is an unlimited amount of each banknote and it's possible to represent any non-negative integer S as some banknote multiset.
Egor has a wallet to keep all the money he has earned. You may think of the wallet as of a banknote sequence. Egor likes to keep the banknotes in his wallet in the non-decreasing order of their costs.
In the beginning, the wallet is empty. Then, each of \(S_i\) is represented as a banknote multiset \(X_i\). Egor calls a sequence \(X_1, X_2, ..., X_n\) an effortless way of getting paid if for each i it's possible to put all the banknotes from \(X_i\) as a subsegment into the current wallet (formed by inserting \(X_1, X_2, ..., X_{i - 1}\) in the same way) so that the banknotes in his wallet are in the non-decreasing order of their costs.
For example, if the current wallet is \([1, 1, 4, 5, 6]\), then it's possible to insert \(X_i = \){\(1, 2, 3, 4\)} the way Egor wants and it's impossible to do the same with \(X_i = \){\(1, 2, 3, 4, 5\)} since the 4 from the wallet doesn't allow to do so.
Your task is calculate the number of effortless ways of getting paid. Two ways are distinct if they aren't equal as sequences of multisets \(X_1, X_2, ..., X_n\).
Input format
The first line of the input contains an integer t denoting the number of test cases.
The first line of the test case description contains two integers n and k. The next line contains k integers denoting \(W_1, W_2, ..., W_k\). The next line contains n integers denoting \(S_1, S_2, ..., S_n\).
Output format
The output should contain a single integer denoting the number of effortless way of getting paid modulo \(1000000009\) (\(10^9 + 9\)).
Constraints
- \(1 \le t \le 6\)
- \(1 \le n \le 100\)
- \(1 \le k \le 10\)
- \(1 = W_1 < W_2 < ... < W_k \le 5000\)
- \(1 \le S_i \le 5000\)
Subtasks
| Extra constraints | Points | Which tests |
|---|---|---|
| \(n \le 5, k \le 4, S_i \le 20\) | 30 | 1 |
| no extra constraints | 70 | 2 |
There are two ways to represent \(S_1 = 6\): {\(1, 1, 1, 1, 1, 1\)} and {\(1, 5\)}. There are also four ways to represent \(S_2 = 11\): {\(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1\)}, {\(1, 1, 1, 1, 1, 1, 5\)}, {\(1, 5, 5\)} and {\(1, 10\)}.
There are \(8 = 2 \times 4\) possible combinations of representations, but one of them is invalid: \(X_1 = \){\(1, 5\)} and \(X_2 = \){\(1, 10\)} is not an effortless way of getting paid.
