کیوان (Keivan)

کیوان مانند تمام المپیاد کامپیوتری‌ها بسیار خرافاتی است. او معتقد است که $k$ عدد در دنیا برای او شانس می‌آورند. اعداد مورد علاقه‌ی او را $b_1, b_2, \ldots, b_k$ می‌نامیم.

کیوان جهت آمادگی در آزمون‌های دوره تابستان تصمیم گرفت تا روی دنباله‌ی $n$ عضوی $a_1, a_2, \ldots, a_n$ یک بازی انجام دهد. در این بازی او عملیات زیر را می‌تواند انجام دهد:

• یک بازه متوالی از اعضای دنباله را انتخاب می‌کند به شرطی که $xor$ اعداد آن بازه، یکی از اعداد مورد علاقه‌اش باشد. به عبارتی بازه‌ی $a_l, a_{l+1}, \ldots, a_r$ را می‌تواند انتخاب کند به شرطی که حداقل یک $i$ وجود داشته باشد که $a_l \oplus a_{l_1} \oplus \ldots \oplus a_r = b_i$ باشد. بعد از اینکه بازه را انتخاب کرد، تمام اعضای آن بازه حذف می‌شوند و بازی با اعداد باقی‌مانده از دنباله ادامه پیدا می‌کند. دقت کنید که پس از حذف یک بازه، اعداد باقی‌مانده دوباره به هم می‌چسبند. برای مثال اگر $a = \{5, 2, 2, 3, 4\}$ و $b = \{1, 6\}$ باشد، او می‌تواند ابتدا بازه‌ی $a_3, a_4$ را حذف کند چون $b_1 = 1$ است تا به دنباله‌ی $a = \{5, 2, 4\}$ برسد. سپس چون $b_2 = 6$ است، بازه‌ی $a_2, a_3$ را حذف کند تا به $a = \{5\}$ برسد.

کیوان می‌خواهد بداند با انجام تعدادی دلخواه از عملیات تعریف شده، آرایه نهایی چند حالت ممکن دارد؟ دو حالت متفاوت در نظر گرفته می‌شوند، اگر و تنها اگر اندیسی وجود داشته باشد که در یک حالت حذف شده باشد و در حالت دیگر حذف نشده باشد. به کیوان کمک کنید تا جواب این سوال را به پیمانه‌ی $10^9+7$ محاسبه کند.

در خط اول دو عدد $n$ و $k$ می‌آیند.

در خط دوم دنباله‌ی $a_1, a_2, \ldots, a_n$ می‌آید.

در خط سوم دنباله‌ی $b_1, b_2, \ldots, b_k$ می‌آید.

در تنها خط خروجی، تعداد حالات ممکن مجموعه‌ی اندیس‌های باقی‌مانده‌ی $a$ را به پیمانه‌ی $10^9+7$ خروجی دهید.

• زیرمسئله اول (۷ نمره): $n \le 18$.
• زیرمسئله دوم (۸ نمره): $a_i, b_i \le 1, n \le 5000$.
• زیرمسئله سوم (۱۳ نمره): $k = 1, b_1 = 0$.
• زیرمسئله چهارم (۲۰ نمره): $k = 1$.
• زیرمسئله پنجم (۳۰ نمره): $k = 2$.
• زیرمسئله ششم (۲۲ نمره): بدون محدودیت اضافی.

• $1 \leq n \le 10^5$
• $1 \le k \le 5$
• $0 \leq a_i, b_i < 128$