لدى Farmer John حقل صغير على شكل شبكة من $N$ صفوف و$N$ أعمدة ($1 \le N \le 2000$)، حيث يُرمز إلى المربع رقم $j$ من اليسار في الصف رقم $i$ من الأعلى بالزوج $(i,j)$، لكل $1 \le i,j \le N$. يريد زراعة الذرة الحلوة والبرسيم الحجازي في حقله. ولتحقيق ذلك، يحتاج إلى تركيب بعض الرشاشات الخاصة.

يروي رشاش الذرة الحلوة الموجود في المربع $(I,J)$ جميع المربعات الواقعة أسفل وإلى اليسار منه: أي المربعات $(i,j)$ التي تحقق $I \le i$ و$j \le J$.

يروي رشاش البرسيم الحجازي الموجود في المربع $(I,J)$ جميع المربعات الواقعة أعلى وإلى اليمين منه: أي المربعات $(i,j)$ التي تحقق $i \le I$ و$J \le j$.

يمكن للمربع الذي يرويه رشاش واحد أو أكثر من رشاشات الذرة الحلوة أن ينبت الذرة الحلوة؛ ويمكن للمربع الذي يرويه رشاش واحد أو أكثر من رشاشات البرسيم الحجازي أن ينبت البرسيم الحجازي. لكن المربع الذي يرويه كلا النوعين من الرشاشات، أو لا يرويه أي منهما، لا يمكنه إنبات أي شيء.

ساعد FJ في تحديد عدد طرق تركيب الرشاشات في حقله، بترديد $10^9 + 7$، بحيث يوجد رشاش واحد على الأكثر في كل مربع، ويكون كل مربع صالحًا للزراعة (أي يرويه نوع واحد بالضبط من الرشاشات).

بعض المربعات تشغلها بالفعل أبقار كثيفة الشعر؛ وهذا لا يمنع تلك المربعات من أن تكون صالحة للزراعة، لكن لا يمكن تركيب رشاشات فيها.

الإدخال

يحتوي السطر الأول على عدد صحيح واحد $N.$

لكل $1\le i\le N,$ يحتوي السطر رقم $i+1$ على سلسلة طولها $N$ تمثل الصف رقم $i$ من الشبكة. كل محرف في السلسلة هو إما 'W' (يشير إلى مربع تشغله بقرة كثيفة الشعر)، أو '.' (مربع غير مشغول).

الإخراج

اطبع باقي قسمة عدد طرق تركيب الرشاشات على $10^9+7.$

أمثلة

الإدخال 1

2
..
..

الإخراج 1

28

ملاحظة

فيما يلي جميع الاحتمالات الأربعة عشر عندما يمكن أن تنبت الذرة الحلوة في $(1,1)$.

CC  .C  CA  CC  .C  CA  CA  C.  CA  C.  CC  .C  CC  .C  
CC, CC, CC, .C, .C, .C, CA, CA, .A, .A, C., C., .., ..

الإدخال 2

4
..W.
..WW
WW..
...W

الإخراج 2

2304

ملاحظة

يحقق هذا قيود المهمة الفرعية الأولى الموصوفة أدناه.

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

• تحقق حالات الاختبار 3–4 الشرط $N\le 10$، ويوجد عشرة مربعات غير مشغولة على الأكثر.
• تحقق حالات الاختبار 5–9 الشرط $N\le 200$.
• لا توجد قيود إضافية على حالات الاختبار 10–16.

مؤلف المسألة: Benjamin Qi