+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مردم شهر دست‌به‌دست هم می‌دهند و یک صف بلند درست می‌کنند. هر شهروند یک عدد بین ۰ تا $M$ برای خودش انتخاب کرده است. عدد شهروند $i$ام برابر $a_i$ است. حال از روی اعداد شهروندان اعداد $t_1, t_2, \dots, t_{n-k+1}$ را به صورت زیر می‌سازیم. $$ a_i \oplus a_{i+1} \oplus \dots \oplus a_{i+k-1} = t_i$$ منظور از $\oplus$ عملگر [$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$ را داریم. از شما می‌خواهیم تعداد حالت‌های ممکن برای اعداد شهروندان را محاسبه کنید. از آن‌جایی که ممکن است پاسخ مسئله خیلی بزرگ باشد، باقی‌مانده‌ی پاسخ مسئله را بر $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 = 0$ است، پس دنباله‌ی $a$ تماماً ۰ است و نمی‌تواند دنباله‌ی $t$ به صورت گفته شده باشد. بنابراین پاسخ مسئله برابر ۰ می‌شود. ## ورودی نمونه ۲ ``` 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 ```