Deskripsi Masalah
JOI-kun adalah siswa kelas $1$ SD. JOI-kun sangat menyukai penjumlahan dan pengurangan yang baru saja dipelajarinya, sehingga setiap kali melihat deretan angka, ia bermain membuat persamaan dengan menyisipkan = di antara $2$ angka terakhir dan selalu menyisipkan + atau - di antara angka-angka lainnya yang bersebelahan. Sebagai contoh, dari 8 3 2 4 8 7 2 4 0 8 8, ia dapat membuat persamaan 8+3-2-4+8-7-2-4-0+8=8.
Setelah membuat persamaan, JOI-kun menghitungnya untuk memastikan apakah persamaan tersebut benar. Namun, JOI-kun belum mengenal bilangan negatif dan tidak dapat menghitung bilangan yang melebihi $20$. Oleh karena itu, di antara persamaan yang benar, hanya persamaan yang ketika ruas kirinya dihitung dari kiri ke kanan menghasilkan bilangan-bilangan antara $0$ hingga $20$ (inklusif) di sepanjang perhitungan sajalah yang dapat dipastikan kebenarannya oleh JOI-kun. Sebagai contoh, 8+3-2-4-8-7+2+4+0+8=8 adalah persamaan yang benar, tetapi karena 8+3-2-4-8 yang muncul di tengah perhitungan adalah bilangan negatif, JOI-kun tidak dapat memastikan apakah persamaan ini benar atau tidak.
Diberikan barisan angka sebagai masukan, buatlah program untuk mencari banyaknya persamaan benar yang dapat dibuat dan dipastikan oleh JOI-kun.
Masukan
Berkas masukan terdiri dari $2$ baris. Baris ke-$1$ berisi sebuah bilangan bulat $N$ ($3 \le N \le 100$) yang menyatakan banyaknya angka yang berderet. Baris ke-$2$ berisi $N$ buah bilangan bulat minimal $0$ dan maksimal $9$ yang dipisahkan oleh spasi.
Pada $60\%$ dari data masukan yang diberikan, banyaknya persamaan benar yang dapat dibuat dan dipastikan oleh JOI-kun tidak melebihi $2^{31}-1$. Selain itu, pada seluruh data masukan yang diberikan, banyaknya persamaan benar yang dapat dibuat dan dipastikan oleh JOI-kun tidak melebihi $2^{63}-1$.
Keluaran
Keluarkan dalam $1$ baris sebuah bilangan bulat yang menyatakan banyaknya persamaan benar yang dapat dibuat dan dipastikan oleh JOI-kun.
Contoh Masukan dan Keluaran
Contoh Masukan 1
11 8 3 2 4 8 7 2 4 0 8 8
Contoh Keluaran 1
10
Contoh Masukan 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
Contoh Keluaran 2
7069052760
Pada Contoh Masukan $1$, JOI-kun dapat membuat dan memastikan $10$ persamaan benar berikut:
8+3-2-4+8-7-2-4-0+8=88+3-2-4+8-7-2-4+0+8=88+3+2+4-8-7+2-4-0+8=88+3+2+4-8-7+2-4+0+8=88+3+2-4+8-7+2+4-0-8=88+3+2-4+8-7+2+4+0-8=88-3+2+4-8+7+2+4-0-8=88-3+2+4-8+7+2+4+0-8=88-3+2-4+8+7+2-4-0-8=88-3+2-4+8+7+2-4+0-8=8
Oleh karena itu, keluarkan $10$.
Pada Contoh Masukan $2$, perhatikan bahwa jawabannya tidak muat dalam rentang bilangan bulat bertanda $32$-bit.
(Tambahan pada tanggal $21$ bulan $2$ tahun $2015$) Berdasarkan masukan dari pengguna, ditemukan adanya kesalahan pada persamaan di dalam penjelasan Contoh Masukan $1$. Saat ini kesalahan tersebut telah diperbaiki. Persamaan ke-$5$ sebelumnya adalah 8+3-2-4+8-7+2+4-0-8=8, dan telah diperbaiki menjadi 8+3+2-4+8-7+2+4-0-8=8. Selain itu, persamaan ke-$6$ sebelumnya adalah 8+3-2-4+8-7+2+4+0-8=8, dan telah diperbaiki menjadi 8+3+2-4+8-7+2+4+0-8=8.