لدى Bessie مصفوفتان بطول $N$ ($1\le N\le500$). العنصر $i$ في الأولى $a_i$ ($1\le a_i\le10^6$)، والثانية $b_i$ ($1\le b_i\le10^6$).

تريد تقسيمهما إلى أجزاء غير فارغة بحيث:

1. كل عنصر ينتمي لجزء واحد بالضبط.
2. كلاهما له العدد نفسه $k$ من الأجزاء.
3. لكل $1\le i\le k$ متوسط الجزء $i$ من اليسار في الأولى أقل من أو يساوي نظيره في الثانية.

احسب التقسيمات بترديد $10^9+7$. تختلف إن اختلف عدد الأجزاء أو انتمى عنصر لجزء آخر.

الإدخال

السطر الأول $N$.

التالي $a_1,a_2,\ldots,a_N$.

التالي $b_1,b_2,\ldots,b_N$.

الإخراج

عدد التقسيمات الصالحة غير الفارغة بترديد $10^9+7$.

أمثلة

الإدخال 1

2
1 2
2 2

الإخراج 1

2

ملاحظة

تقسيمان صالحان، الأولى ثم الثانية:

1. $[1],[2]$ / $[2],[2]$.
2. $[1,2]$ / $[2,2]$.

الإدخال 2

3
1 3 2
2 2 2

الإخراج 2

3

ملاحظة

ثلاثة تقسيمات صالحة، الأولى ثم الثانية:

1. $[1,3],[2]$ / $[2,2],[2]$.
2. $[1,3],[2]$ / $[2],[2,2]$.
3. $[1,3,2]$ / $[2,2,2]$.

الإدخال 3

5
2 5 1 3 2
2 1 5 2 2

الإخراج 3

1

ملاحظة

التقسيم الوحيد، الأولى ثم الثانية: $[2],[5,1,3],[2]$ / $[2],[1,5],[2,2]$.

الإدخال 4

7
3 5 2 3 4 4 1
5 3 5 3 3 4 1

الإخراج 4

140

المهام الفرعية

• المدخلات 5–6: $N\le10$.
• المدخلات 7–9: $N\le80$.
• المدخلات 10–17: $N\le300$.
• المدخلات 18–20: $N\le500$.

صاحب المسألة: Alex Liang