در درس زیست‌شناسی آمده که مورچه‌ها هرگاه به‌هم می‌رسند اسم یکدیگر را بلند صدا زده و به هم سلام می‌کنند. شما که مدت‌هاست به مطالب این درس شک کرده‌اید، می‌خواهید با انجام یک آزمایش صحت مطالب آن را بررسی کنید.

در این آزمایش، تعدادی مورچه روی یک خط‌کش بسیار باریک قرار گرفته‌اند و روی آن حرکت می‌کنند. هر مورچه رو به یکی از دو سر خط‌کش با سرعتی نامعلوم در حال حرکت است، و هر لحظه که بخواهد می‌تواند جهت و یا سرعت خودش را عوض کند. مورچه‌ها به خط‌کش علاقه خاصی دارند و برای همین هیچ‌گاه از روی آن خارج نمی‌شوند.

شما یک ضبط‌صوت در کنار خط‌کش قرار داده‌اید، اگر دو مورچه شماره‌ی هم را صدا بزنند و به هم سلام کنند، ضبط‌صوت شما اسم آن دو را ضبط می‌کند. هر دو مورچه‌ای که به هم می‌رسند ابتدا شماره‌ی همدیگر را صدا کرده و سلام می‌کنند و سپس از یکدیگر رد می‌شوند. طبق مطالب درس زیست‌شناسی می‌دانیم که مورچه‌ها در هیچ موقع دیگری اسم یکدیگر را صدا نمی‌زنند و همچنین حرکت مورچه‌ها به نحوی است که هرگز بیشتر از ‎۲‎ مورچه همزمان از کنار هم رد نمی‌شوند.

شما مدتی ضبط‌صوت را روشن گذاشته و به دنبال کارهای مهم‌ترتان رفته‌اید. بعد از برگشتن به محل آزمایش متوجه می‌شوید که فراموش کرده بودید که مکان اولیه مورچه‌ها را یادداشت کنید. شما با در دست داشتن رشته‌ای از جفت‌های متشکل از شماره‌ی مورچه‌ها، یعنی اطلاعات ضبط‌صوت، می‌خواهید بدانید چند حالت اولیه وجود داشته که می‌توانسته چنین رشته‌ای تولید کند. یک حالت اولیه یعنی یک جایگشت از شماره‌ی مورچه‌ها که نشان می‌دهد ترتیب قرارگیری مورچه‌ها در ابتدای کار چه بوده است.

برنامه‌ای بنویسید که

• تعداد مورچه‌ها و تعداد جفت‌های نام روی ضبط‌صوت را از ورودی بخواند.
• سپس جفت شماره‌های روی ضبط‌صوت را به‌ترتیبی که ضبط شده‌اند بخواند.
• تعداد حالات اولیه قرارگیری مورچه‌ها که امکان ایجاد چنین دنباله‌ای روی ضبط‌صوت داشته را پیدا کند.
• باقی‌مانده این عدد را بر ‎$100003$‎ در خروجی بنویسد.

• در سطر اول ورودی تعداد مورچه‌ها‎($n$)‎ و تعداد جفت‌های ضبط‌شده ‎($m$)‎ آمده است‎.‎
• در هر یک از ‎$m$‎ سطر بعدی شماره‌ی ‎۲‎ مورچه که به‌هم رسیده‌اند قرار گرفته که با یک فاصله از هم جدا شده‌اند.
• این جفت شماره‌ها به ترتیب زمان رخدادنشان آمده است.
• $2 \le n \le 2000$‎.
• ‎ $0 \le m \le 100000$‎.
• شماره‌ی مورچه‌ها از ‎$1$‎ تا ‎$n$‎ می‌باشد.

در تنها سطر خروجی باقی‌مانده تعداد حالت‌های اولیه ممکن را بر عدد ‎$100003$‎ چاپ کنید.

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

• سوال بعد
• سوال قبل