โจทย์ปัญหา

JOI คุงเป็นนักเรียนชั้นประถมศึกษาปีที่ $1$ JOI คุงชอบการบวกและการลบที่เพิ่งเรียนมามาก เมื่อเห็นตัวเลขเรียงกัน เขาจะเล่นสร้างสมการโดยใส่เครื่องหมาย = ระหว่างตัวเลข $2$ ตัวสุดท้าย และใส่เครื่องหมาย + หรือ - ระหว่างตัวเลขที่เหลือแต่ละคู่เสมอ ตัวอย่างเช่น จาก 8 3 2 4 8 7 2 4 0 8 8 สามารถสร้างสมการ 8+3-2-4+8-7-2-4-0+8=8 ได้

หลังจากสร้างสมการแล้ว JOI คุงจะคำนวณเพื่อตรวจสอบว่าสมการนั้นเป็นสมการที่ถูกต้องหรือไม่ อย่างไรก็ตาม JOI คุงยังไม่รู้จักจำนวนลบ และไม่สามารถคำนวณจำนวนที่เกิน $20$ ได้ ดังนั้น ในบรรดาสมการที่ถูกต้อง เฉพาะสมการที่เมื่อคำนวณฝั่งซ้ายจากซ้ายไปขวาแล้ว จำนวนที่ปรากฏระหว่างการคำนวณทั้งหมดมีค่าตั้งแต่ $0$ ถึง $20$ เท่านั้น จึงจะเป็นสมการที่ถูกต้องซึ่ง JOI คุงสามารถตรวจสอบได้ ตัวอย่างเช่น 8+3-2-4-8-7+2+4+0+8=8 เป็นสมการที่ถูกต้อง แต่เนื่องจาก 8+3-2-4-8 ที่ปรากฏระหว่างการคำนวณเป็นจำนวนลบ JOI คุงจึงไม่สามารถตรวจสอบได้ว่าสมการนี้ถูกต้องหรือไม่

เมื่อกำหนดลำดับของตัวเลขมาให้เป็นข้อมูลนำเข้า จงเขียนโปรแกรมเพื่อหาจำนวนสมการที่ถูกต้องซึ่ง JOI คุงสามารถสร้างและตรวจสอบได้

ข้อมูลนำเข้า

ไฟล์ข้อมูลนำเข้าประกอบด้วย $2$ บรรทัด บรรทัดที่ $1$ มีจำนวนเต็ม $N$ ($3 \le N \le 100$) แทนจำนวนตัวเลขที่เรียงกัน บรรทัดที่ $2$ มีจำนวนเต็มตั้งแต่ $0$ ถึง $9$ จำนวน $N$ ตัว คั่นด้วยช่องว่าง

ใน $60\%$ ของข้อมูลนำเข้าที่กำหนดให้ จำนวนสมการที่ถูกต้องซึ่ง JOI คุงสามารถสร้างและตรวจสอบได้จะไม่เกิน $2^{31}-1$ และในข้อมูลนำเข้าทั้งหมดที่กำหนดให้ จำนวนสมการที่ถูกต้องซึ่ง JOI คุงสามารถสร้างและตรวจสอบได้จะไม่เกิน $2^{63}-1$

ข้อมูลส่งออก

จงแสดงผลจำนวนเต็มที่แทนจำนวนสมการที่ถูกต้องซึ่ง JOI คุงสามารถสร้างและตรวจสอบได้ใน $1$ บรรทัด

ตัวอย่างข้อมูลนำเข้าและข้อมูลส่งออก

ตัวอย่างข้อมูลนำเข้า 1

11
8 3 2 4 8 7 2 4 0 8 8

ตัวอย่างข้อมูลส่งออก 1

10

ตัวอย่างข้อมูลนำเข้า 2

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1

ตัวอย่างข้อมูลส่งออก 2

7069052760

ในตัวอย่างข้อมูลนำเข้า $1$ JOI คุงสามารถสร้างและตรวจสอบสมการที่ถูกต้องได้ $10$ สมการดังนี้:

• 8+3-2-4+8-7-2-4-0+8=8
• 8+3-2-4+8-7-2-4+0+8=8
• 8+3+2+4-8-7+2-4-0+8=8
• 8+3+2+4-8-7+2-4+0+8=8
• 8+3+2-4+8-7+2+4-0-8=8
• 8+3+2-4+8-7+2+4+0-8=8
• 8-3+2+4-8+7+2+4-0-8=8
• 8-3+2+4-8+7+2+4+0-8=8
• 8-3+2-4+8+7+2-4-0-8=8
• 8-3+2-4+8+7+2-4+0-8=8

ดังนั้นจึงแสดงผลเป็น $10$

ในตัวอย่างข้อมูลนำเข้า $2$ โปรดสังเกตว่าคำตอบมีค่าเกินขอบเขตของจำนวนเต็มแบบมีเครื่องหมายขนาด $32$ บิต

(เพิ่มเติมเมื่อวันที่ $21$ เดือน $2$ ปี $2015$) จากการแจ้งของผู้ใช้งาน พบว่ามีข้อผิดพลาดในสมการที่อยู่ในคำอธิบายของตัวอย่างข้อมูลนำเข้า $1$ ซึ่งขณะนี้ได้แก้ไขเรียบร้อยแล้ว สมการลำดับที่ $5$ เดิมคือ 8+3-2-4+8-7+2+4-0-8=8 ได้แก้ไขเป็น 8+3+2-4+8-7+2+4-0-8=8 และสมการลำดับที่ $6$ เดิมคือ 8+3-2-4+8-7+2+4+0-8=8 ได้แก้ไขเป็น 8+3+2-4+8-7+2+4+0-8=8