• محدودیت زمان: ۴ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

شهر اعداد که پیشتر پادشاه و مجلس را انتخاب کرده‌بود ولی به نتیجه نرسیده‌بود، تصمیم به انتخاب خود گرفت. آن‌ها بالاخره دریافتند که برای اینکه جامعه‌ای متعالی داشته باشند این مردم هستند که باید دست‌به‌دست هم داده و جامعه خود را آباد کنند.

از این رو مردم شهر دست‌به‌دست هم می‌دهند و یک صف بلند درست می‌کنند و حال هر $k$ نفر متوالی در صف وظیفه‌ای بر عهده ‌می‌گیرند. به طور دقیق‌تر اگر شهر را $n$ نفر تشکیل دهند، $n-k+1$ وظیفه خواهیم داشت که وظیفه شماره $i$ بر عهده افراد $i$، $i+1$، $\dots$ تا $i+k-1$ خواهد بود.

همچنین وظیفه $i$ یک عدد $t_i$ دارد و تنها افرادی می‌توانند آن را به درستی انجام دهند که $xor$ عدد آن‌ها برابر $t_i$ شوند. یا به طور دقیق‌تر اگر دنباله اعداد شهر را $a$ بگیریم، آنها از عهده وظیفه‌ با $i$ بر‌ می‌آیند اگر:

$$ a_i \oplus a_{i+1} \oplus \dots \oplus a_{i+k-1} = t_i$$

همچنین شهر برای جلوگیری از اختلاف طبقاتی یک عدد $M$ دارد که نشانگر بیشینه مجاز برای یک شهروند است. حال به مردم بگویید که چند دنباله معتبر به پیمانه $10^9 + 7$ برای مردم شهر وجود دارد تا همگی از پس وظایف خود برایند.

ورودی

در سطر اول به ترتیب سه عدد $n$ تعداد شهروندان و $k$ تعداد همکاران هر وظیفه و $M$ بیشینه مجاز برای شهروندان می‌آید. (توجه کنید شهر اعداد را اعداد صحیح نامنفی می‌سازند.) $$1 \le k \le n \le 5000$$

سپس در سطر بعد $n-k+1$ عدد می‌آید که عدد $i$ـم نشانگر $t_i$ است.

$$0 \le M, t_i \le 5000$$

زیرمسئله‌ها

زیرمسئله	‌ محدودیت‌ها	امتیاز
۱	$1 \le k \le 3$ و $1\le k \le n \le 100$ و $0 \le M, t_i \le 100$	۲۰
۲	$1 \le k \le n \le 200$ و $0 \le M, t_i \le 100$	۵۰
۳	بدون محدودیت اضافه	۳۰

خروجی

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

مثال

ورودی نمونه ۱

4 2 0
0 1 1

خروجی نمونه ۱

0

از آن‌جا که $M$ برابر ۰ است پس همه اعضای دنباله باید دقیقا۰ باشند و این در تضاد با وظیفه دوم است که در آن‌ها گفته شده $xor$ عضو دوم و سوم باید ۱ باشد.

ورودی نمونه ۲

3 3 2
1

خروجی نمونه ۲

7

توضیح نمونه ۲

دنباله‌های مطلوب:

• $0, 0, 1$
• $0, 1, 0$
• $1, 0, 0$
• $1, 1, 1$
• $1, 2, 2$
• $2, 1, 2$
• $2, 2, 1$

ورودی نمونه ۳

25 23 89
22 37 41

خروجی نمونه ۳

809594952