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 Si credits. Egor will be getting money for the projects according to the order, i.e. first he will get S1 credits, then S2 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 Wi 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 Si is represented as a banknote multiset Xi. Egor calls a sequence X1,X2,...,Xn an effortless way of getting paid if for each i it's possible to put all the banknotes from Xi as a subsegment into the current wallet (formed by inserting X1,X2,...,Xi−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 Xi={1,2,3,4} the way Egor wants and it's impossible to do the same with Xi={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 X1,X2,...,Xn.
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 W1,W2,...,Wk. The next line contains n integers denoting S1,S2,...,Sn.
The output should contain a single integer denoting the number of effortless way of getting paid modulo 1000000009 (109+9).
Extra constraints | Points | Which tests |
---|---|---|
n≤5,k≤4,Si≤20 | 30 | 1 |
no extra constraints | 70 | 2 |
There are two ways to represent S1=6: {1,1,1,1,1,1} and {1,5}. There are also four ways to represent S2=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×4 possible combinations of representations, but one of them is invalid: X1={1,5} and X2={1,10} is not an effortless way of getting paid.