Ваня нүд болгон нь $0$, $1$, $2$ эсвэл $3$ гэсэн утгатай нэг шаар агуулах $n × n$ хэмжээ бүхий талбай дээр тоглоом тоглож байв. Уг тоглоомын зорилго нь хэрээс дээрх шаарнуудын утгуудын үржвэр нь боломжит хамгийн их байхаар нэг хэрээсийг устгах явдал юм. Хэрээс нь 2 төрөлтэй ба үүнд: энгийн болон эргэсэн хэрээс гэсэн 2 төрөл байна. Жишээлбэл:

**o**  
**o**  
ooooo  
**o**  
**o**

эсвэл

o***o  
*o*o*  
**o**  
*o*o*  
o***o

Илүү дэлгэрэнгүй тайлбарлавал, хэрээс гэдэг нь $d ≤ r, c ≤ n - d + 1$ байх 3 бүхэл тоо $r$, $c$ болон $d$-ээр өгөгдөнө. Энгийн хэрээс нь $|x - r|*|y - c| = 0$ болон $|x - r| + |y - c| < d$ байх $(x, y)$ (энд $x$ нь мөрийн дугаарыг, $y$ нь баганын дугаарыг илэрхийлнэ) нүднүүд дээр орших шаарнуудаас тогтдог. Эргэсэн хэрээс нь $|x - r| = |y - c|$ болон $|x - r| < d$ байх $(x, y)$ нүднүүд дээр орших шаарнуудаас тогтдог ажээ.

Ваня нэг хэрээс дээрх шаарнуудын утгуудын үржвэрийн боломжит хамгийн их утгыг олохыг хүсжээ. Уг утга нь маш том байж болох учраас хариултыг $10^{9} + 7$ модулаар бодон хэвлэнэ үү.

Оролт

Эхний мөрөнд шаартай хүснэгтийн мөр болон баганын тоог илэрхийлэх бүхэл тоо $n$ ($1 ≤ n ≤ 1000$) өгөгдөнө.

Дараагийн $n$ мөрийн мөр болгонд '$0$', '$1$', '$2$' эсвэл '$3$' байх $n$ ширхэг тэмдэгтүүд өгөгдөх ба эдгээр нь шаарнуудын утгуудыг илэрхийлнэ.

Гаралт

Шаарнуудын утгуудын үржвэрийн боломжит хамгийн их утгыг $10^{9} + 7$ модулаар бодон хэвлэнэ үү. Та $10^{9} + 7$ модулаар бодсон үлдэгдлийг хамгийн их байлгах ёсгүйг анхаарна уу. Та хамгийн их утгыг олоод түүнийг уг модулаар бодон хэвлэх ёстой юм.

Эхний жишээнд шаарнуудын утгуудын үржвэрийн боломжит хамгийн их утгыг $(3, 3)$ гэсэн нүд дээр төвтэй, $1$ гэсэн радиустай эргэсэн хэрээсийг устгаснаар гаргаж чадах ба хамгийн их утга нь $2*2*3*3*3 = 108$ байна.