অসীমের গোলকধাঁধায় স্বাগতম!
দুর্ভাগ্যবশত তুমি এখন এই গোলকধাঁধায় আটকে গিয়েছ এবং তুমি এখান থেকে বের হতে চাও। কিন্তু এর জন্য তোমাকে চাবি দিয়ে কিছু তালা খুলতে হবে। তোমাকে $Q$ সংখ্যক তালা দেওয়া হয়েছে যেগুলো একেকটা পূর্ণসংখ্যা $x_i$। ভাগ্যক্রমে তোমার কাছে $N$ সংখ্যক পূর্ণসংখ্যার একটি অ্যারে আছে যাকে $a_1, a_2, a_3, ..., a_n$ হিসেবে সংজ্ঞায়িত করা যায়। একটা তালা $x_i$ এর চাবি হলো ঐ অ্যারের খালি নয় এমন উপসেট যাকে $s_1, s_2, ..., s_k$ হিসেবে সংজ্ঞায়িত করা যায় এবং যেন $x_i \mathbin{\&} (s_1 \mathbin{|} s_2 \mathbin{|} ... \mathbin{|} s_k) == 0$ হয়, যেখানে $\mathbin{\&}$ মানে বিটওয়াইজ-AND এবং $\mathbin{|}$ মানে বিটওয়াইজ-OR অপারেশন। কিন্তু, যেহেতু তুমি একজন প্রব্লেম সলভার, তাই তুমি জানতে চাও তোমার অ্যারেতে এরকম কয়টা উপসেট আছে যেটা তালা $x_i$ এর একেকটা চাবি।
এই সংখ্যা অনেক বড় হতে পারে। তাই, তোমাকে সেই সংখ্যা $modulo$ $1000000007$ বের করতে হবে। যেখানে $modulo$ অপারেশন হচ্ছে এই সংখ্যাকে $1000000007$ দ্বারা ভাগ করলে যা ভাগশেষ থাকে।
Input
ইনপুট শুরু হবে একটি পূর্ণসংখ্যা $T$ দ্বারা, যা টেস্টকেস সংখ্যা নির্দেশ করে।
প্রতি টেস্টকেস শুরু হবে দুইটি পূর্ণসংখ্যা $N$ ও $Q$ দ্বারা, যা তোমার অ্যারেতে পূর্ণসংখ্যার মোট সংখ্যা এবং মোট তালার সংখ্যা নির্দেশ করে।
এর পরের লাইনে $N$টি পূর্ণসংখ্যা $a_i$ থাকবে।
এর পরের $Q$ লাইনের প্রতিটিতে একটি পূর্ণসংখ্যা $x_i$ থাকবে, যেগুলো একেকটা তালা।
Constraints
$T (1 ≤ T ≤ 5)$$N (1 ≤ N ≤ 10^5)$$Q (1 ≤ Q ≤ 10^5)$$a_i (1 ≤ a_i ≤ 10^6)$$x_i (1 ≤ x_i ≤ 10^6)$
সাবটাস্ক ১ (১০ পয়েন্টস)
$T (1 ≤ T ≤ 5)$, $N (1 ≤ N ≤ 15)$, $Q (1 ≤ Q ≤ 10^5)$, $a_i (1 ≤ a_i ≤ 10^6)$, $x_i (1 ≤ x_i ≤ 10^6)$
সাবটাস্ক ২ (৩০ পয়েন্টস)
$T (1 ≤ T ≤ 5)$, $N (1 ≤ N ≤ 10^4)$, $Q (1 ≤ Q ≤ 10^5)$, $a_i (1 ≤ a_i ≤ 10^3)$, $x_i (1 ≤ x_i ≤ 10^3)$
সাবটাস্ক ৩ (৬০ পয়েন্টস)
আসল কন্সট্রেইন্টস
Output
প্রতি কেসের জন্য "Case T:"(উদ্ধৃতি চিহ্ন ছাড়া) প্রিন্ট করতে হবে, যেখানে $T$ হচ্ছে টেস্টকেস সংখ্যা।
পরের $Q$ লাইনের প্রতিটিতে একটা পূর্ণসংখ্যা $y_i$ থাকবে, যা তালা $x_i$ এর বৈধ চাবি সংখ্যা $modulo$ $1000000007$ নির্দেশ করে।
Sample
| 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 |
