+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- محمدرضا وقتی به زندان افتاد، از دانشگاه اخراجش کردند. حالا محمدرضا بعد از چند سال و بعد از گذراندن دوران مقدس سربازی می‌خواد دوباره کنکور بده و بره دانشگاه. اون خیلی هم اصرار داره که حتما دانشگاه شریف بره. فقط مشکل اینه که محمدرضا خیلی استعداد نداره. اون بعد از دادن کنکور می‌فهمه که دقیقا آخر شده. حالا می‌خواد انتخاب رشته کنه. به غیر از محمدرضا $n$ نفر در کنکور شرکت کردن. هر نفر در برگه‌ی انتخاب رشتش دقیقا $k$رشته از رشته‌های داشنگاه شریفو انتخاب کرده که به ترتیب بررسی می‌شن. یعنی اگر یک نفر رشته‌ی اولی که انتخاب کرده رو قبول شه(هنوز ظرفیت داشته باشه) دیگه به سراغ رشته‌های بعدی نمیرن و همون رشته‌رو قبول میشه. به همین شکل انقدر از روی لیست انتخاب رشتش میرن جلو تا برسن به رشته‌ای که هنوز ظرفیت داره و اونجا قبول میشه. در کل هم ممکنه که یک نفر کلا در هیچ دانشگاهی قبول نشه که اینطوری باید بخونه برا سال بعد یا بره سربازی. در کل توی دانشگاه شریف $m$ رشته وجود داره. رشته‌ی $i$م، $a_i$ نفر ظرفیت داره. حالا محمدرضا می‌خواد ببینه چند حالت وجود داره که انتخاب رشته بکنه و رشته‌ای رو قبول شه. دوتا انتخاب رشته متفاوت هستند اگر توی لیست انتخاب رشته‌ها یک $i$ وجود داشته باشه که رشته‌ی $i$م در دو لیست متفاوت باشند. دقت کنید محمدرضا انقدر می‌فهمه که رشته‌ی تکراری تو لیستش نزاره. چون ممکنه تعداد حالات خیلی زیاد شه محمدرضا فقط باقی‌مانده‌ی این عدد بر $10^9 + 7$ میخواد. # ورودی در خط اول ورودی سه عدد $n$ و $m$ و $k$ آمده است که به ترتیب نمایانگر تعداد شرکت کننده‌ها در کنکور(بدون احتساب محمدرضا)، تعداد رشته‌های دانشگاه شریف و تعداد انتخاب‌های هرنفر است. در خط بعدی $m$ عدد آمده‌است که عدد $i$م نمایانگر ظرفیت رشته‌ی $i$ است. ظرفیت هر رشته حداکثر یک میلیون است. سپس در $n$ خط بعدی در هر خط $k$ عدد آمده است. خط $i$م نشان‌دهنده‌ی انتخاب رشته‌ی رتبه‌ی $i$م است. عدد اول در هر خط انتخاب اول، عدد دوم انتخاب دوم و به همین شکل عدد $k$م انتخاب $k$م هر نفر است. اعداد داده شده همگی طبیعی و کوچکتر مساوی $m$ هستند. ممکن است در انتخاب رشته‌ی یک نفر از یک رشته چند بار بیاید. $$ 1 \le n,m \le 1000 $$ $$ 1 \le k \le 100 \le m$$ # خروجی فقط یک عدد خروجی دهید که باقی‌مانده‌ی تعداد حالات انتخاب رشته‌ی محمدرضا بر $10^9 + 7$ را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 6 3 2 2 2 2 1 2 2 3 1 3 1 2 2 3 3 1 ``` ## خروجی نمونه ۱ ``` 0 ``` ## ورودی نمونه ۲ ``` 3 3 2 2 1 1 1 2 2 3 2 3 ``` ## خروجی نمونه ۲ ``` 4 ``` روش‌های انتخاب محمدرضا که بتونه قبول شه ایناس: 1 2 - 1 3 - 2 1- 3 1