+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + منبع: آزمون مقدماتی اول دوره ۲۶ المپیاد کامپیوتر ---------- باشگاه هکر‌‌های جوان، مدرسه‌ای برای تربیت هکر‌ها است. در مراسم فارغ‌التحصیلی باشگاه، که به کلاه‌گذاری معروف است، هکر‌ها در یک صف می‌ایستند و بر روی سر هر کدام از آن‌ها یک کلاه می‌گذارند که آینده‌ی آن‌ها را مشخص خواهد کرد. کلا‌ه‌ها سفید یا سیاه هستند. کلاه‌سفید‌ها هدف کمک به جامعه و کلاه‌سیاه‌ها هدف دیگری (؟) دارند. تعداد فارغ‌التحصیلان امسال $n$ نفر است و در انبار $w$ کلاه سفید و $b$ کلاه سیاه وجود دارد. همه‌ی دانش‌آموختگان نیز از موجودی انبار باخبر هستند. در صف، هر فرد تنها از رنگ کلاه افراد جلویی‌اش با‌خبر است و حتی رنگ کلاه خودش را نمی‌داند. یعنی فردی که در ابتدای صف ایستاده، رنگ کلاه هیچ‌کس را نمی‌داند و فردی که در انتهای صف است، رنگ کلاه همه به جز خودش را می‌داند. در انتهای مراسم کلاه‌گذاری، افراد یک به یک و از انتهای صف از مراسم خارج می‌شوند. هر فرد قبل از خارج شدنش اگر از رنگ کلاهش مطمئن باشد، رنگ کلاهش را اعلام می‌کند و به عنوان جایزه پیتزا می‌گیرد (گفتنی است که هکر‌ها، علاقه‌ی شدید به پیتزا دارند!). البته به خاطر کمبود بودجه باشگاه، فقط به اولین فردی که رنگ کلاهش را درست تشخیص بدهد، پیتزا می‌دهند. اگر فردی نیز از رنگ کلاهش مطمئن نباشد، بلند و با افتخار اعلام می‌کند که رنگ کلاهش را نمی‌داند تا افراد باقی‌مانده در مراسم (افرادی که در صف جلوی او قرار داشتند) را نیز از نگون‌بختی‌اش مطلع کند. امیر نفر $i$ ام صف از انتها است. برای نمونه اگر امیر در انتهای صف باشد، $i=1$ است. در چند حالت از کلاه‌گذاری هکر‌ها، امیر صاحب پیتزا می‌شود؟ دو کلاه‌گذاری متفاوت هستند اگر هکری وجود داشته باشد که در یکی از آن‌ها، کلاه‌سفید و در دیگری کلاه‌سیاه باشد. با توجه به این‌که این مقدار می‌تواند بزرگ باشد، باقی‌مانده آن را بر $10^9 + 7$ حساب کنید. **به توضیحات ورودی و خروجی‌های نمونه توجه کنید!** # ورودی در سطر اول ورودی به ترتیب چهار عدد صحیح و نامنفی $b$، تعداد کلاه‌های سیاه، $w$، تعداد کلاه‌های سفید، $n$، تعداد فارغ‌التحصیلان و $i$، مکان امیر نسبت به انتهای صف آمده است. $$0\leq b, w, n\leq 2\ 000$$ $$1\leq i\leq n\leq b + w$$ # خروجی در تنها سطر خروجی، پاسخ مسئله را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۳۰ | $b,w,n \leq 20$ | | ۲ | ۷۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 1 1 2 1 ``` ## خروجی نمونه ۱ ``` 2 ``` در این نمونه یک کلاه سفید و یک کلاه سیاه موجود است پس رنگ کلاه نفر اول و دوم متفاوت است. وقتی از نفر اول رنگ کلاهش را می‌پرسند با دیدن رنگ کلاه نفر بعد و دانستن اینکه از هر رنگ فقط یک کلاه وجود دارد می‌تواند رنگ کلاه خود را مشخص کند. ## ورودی نمونه ۲ ``` 1 1 2 2 ``` ## خروجی نمونه ۲ ``` 0 ``` ## ورودی نمونه ۳ ``` 2 1 2 1 ``` ## خروجی نمونه ۳ ``` 1 ``` ## ورودی نمونه ۴ ``` 2 2 3 2 ``` ## خروجی نمونه ۴ ``` 4 ``` در این نمونه یکی از حالت‌های ممکن این است که رنگ کلاه نفر اول و سوم سفید و رنگ کلاه نفر دوم سیاه باشد. در این حالت ابتدا از نفر اول می‌خواهند تا رنگ کلاهش را بگوید. نفر اول در جلوی خودش یک کلاه سفید و یک کلاه سیاه می‌بیند و می‌داند در کل دو کلاه سفید و دو کلاه سیاه وجود دارد. پس از رنگ کلاه خود مطمئن نیست و با افتخار این موضوع را اعلام می‌کند. پس از آن از نفر دوم می‌خواهند تا رنگ کلاهش را بگوید. نفر دوم در جلوی خود یک کلاه سفید می‌بیند. از طرفی می‌داند که نفر اول نتوانسته رنگ کلاه خود را بگوید پس به این نتیجه می‌رسد که رنگ کلاهش سفید نیست چون اگر سفید می‌بود نفر قبلی با دیدن دو کلاه سفید به این نتیجه می‌رسید که رنگ کلاهش سیاه است. پس نفر دوم می‌گوید که رنگ کلاهش سیاه است و پیتزا را دریافت می‌کند.