Dat je prirodan broj sa ~N~ cifara. Potrebno je sa dve uspravne crte podeliti dati broj, tako da zbir tako dobijena tri broja bude deljiv sa 4. Na koliko različitih načina se to može uraditi?

Opis ulaza

U prvoj liniji standardnog ulaza nalazi se broj ~N~ (~3 \le N \le 10^5~) koji označava broj cifara zadatog broja.
U drugoj liniji standardnog ulaza nalazi se ~N~ karaktera koji označavaju cifre zadatog broja.

Opis izlaza

U prvoj i jedinoj liniji standardnog izlaza ispisati broj različitih načina da se broj podeli uspravnim crtama, tako da zbir dobijenih brojeva bude deljiv sa 4.

Primer 1

Ulaz

5
12345

Izlaz

4

Primer 2

Ulaz

4
7121

Izlaz

1

Objašnjenje test primera:

U prvom test primeru broj je moguće podeliti ukupno na 6 načina:

1) 1 | 2 | 345

2) 1 | 23 | 45

3) 1 | 234 | 5

4) 12 | 3 | 45

5) 12 | 34 | 5

6) 123 | 4 | 5

Samo u slučajevima 1,3,4 i 6, zbir dobijena tri broja biće deljiv sa 4

U drugom test primeru jedina odgovarajuća podela je 7 | 12 | 1

Ograničenja i podzadaci

~3 \le N \le 10^5~

Test primeri su podeljeni u 3 disjunktne grupe:

• U test primerima vrednim 12 poena: ~N \le 18~.
  
• U test primerima vrednim 28 poena: ~N \le 3000~
  
• U test primerima vrednim 60 poena: Nema dodatnih ograničenja.
  

Napomena

Na ulazu je zadat prirodan broj, dakle neće imati vodeće nule. Prilikom podele broja crtama, moguće je dobiti brojeve sa vodećim nulama.