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

یک قاب داریم که آن را شکسته‌ایم. قطعات شکسته شده $n$ مستطیل هستند. یعنی قطعه‌ی $i$ام یک مستطیل $w_i \times h_i$ است. می‌خواهیم آن‌ها را کنار هم بگذاریم و یک قاب مربعی بسازیم. باید قطعات را موازی محورها قرار دهیم.

توجه کنید ممکن است یک قطعه را دوران ۹۰ درجه بدهیم ولی در نهایت باید موازی محورها شود. قطعات مستطیل‌ها را یکسان در نظر بگیرید. برای بهتر متوجه شدن سوال به نمونه‌ها توجه کنید.

ورودی

در سطر اول ورودی، عدد صحیح و مثبت $n$ داده می‌شود که تعداد قطعات نشان می‌دهد. $$1 \leq n \leq 6$$

در $n$ سطر بعدی، در هر سطر دو عدد صحیح و مثبت $h_i$ و $w_i$ داده می‌شود که عرض و ارتفاع یک قطعه را نشان می‌دهد. $$1 \leq w_i, h_i \leq 10$$

خروجی

در یک سطر، تعداد حالت‌هایی که این قطعات را در یک قاب مربعی موازی محورها بگذاریم را چاپ کنید.

مثال‌ها

ورودی نمونه ۱

3
3 4
1 5
4 2

خروجی نمونه ۱

8

ورودی نمونه ۲

4
2 2
2 2
2 2
2 2

خروجی نمونه ۲

1