+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *شهر اعداد که پیشتر پادشاه و مجلس را **انتخاب** کرده‌بود ولی به نتیجه نرسیده‌بود، تصمیم به انتخاب **خود** گرفت. آن‌ها بالاخره دریافتند که برای اینکه جامعه‌ای متعالی داشته باشند این مردم هستند که باید دست‌به‌دست هم داده و جامعه خود را آباد کنند.* از این رو مردم شهر دست‌به‌دست هم می‌دهند و یک صف بلند درست می‌کنند و حال هر $k$ نفر متوالی در صف وظیفه‌ای بر عهده ‌می‌گیرند. به طور دقیق‌تر اگر شهر را $n$ نفر تشکیل دهند، $n-k+1$ وظیفه خواهیم داشت که وظیفه شماره $i$ بر عهده افراد $i$، $i+1$، $\dots$ تا $i+k-1$ خواهد بود. همچنین وظیفه $i$ یک عدد $t_i$ دارد و تنها افرادی می‌توانند آن را به درستی انجام دهند که [$xor$](https://fa.wikipedia.org/wiki/%DB%8C%D8%A7%DB%8C_%D8%A7%D9%86%D8%AD%D8%B5%D8%A7%D8%B1%DB%8C) عدد آن‌ها برابر $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 ``` <details class="blue"> <summary> توضیح نمونه ۲ </summary> دنباله‌های مطلوب: + $0, 0, 1$ + $0, 1, 0$ + $1, 0, 0$ + $1, 1, 1$ + $1, 2, 2$ + $2, 1, 2$ + $2, 2, 1$ </details> ## ورودی نمونه ۳ ``` 25 23 89 22 37 41 ``` ## خروجی نمونه ۳ ``` 809594952 ```