ל־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