Welcome to Osim's maze!
Unfortunately, you are in the maze right now and you want to come outside the maze. But, in order to do that, you have to unlock some locks with keys. So, you are given locks each of which is some integer . You have an array of integers: , , , …, . A key for a lock is some non-empty subset of any positive size containing , , …, of the array such that , where means and means . But, as you are a problem solver, you wonder how many subsets of your array exist as keys for a lock .
Since the answer can be too large, you have to find the number modulo 1000000007.
Input starts with an integer (), denoting the number of test cases. Each case contains two integers () and (), denoting the number of elements of the array and the number of locks.
The next line contains integers , , …, ().
Each of the following lines contains an integer (), denoting a lock of the maze.
For each test case, print "Case T:" (without quote) in the first line, where is the case number. Each of the next lines should contain a single integer , denoting the number of valid keys exist in the array modulo 1000000007 for the lock .
Input | Output |
---|---|
2 4 1 1 2 3 4 4 4 2 2 2 3 5 5 2 | Case 1: 7 Case 2: 3 1 |