#9173. 酥饼

$n$ 个盒子从左往右依次排在桌子上，从左往右第 $i$ 个盒子中有 $a_i$ 个酥饼。

猪打算选择一个区间 $[l,r](1\le l\le r\le n)$，将第 $l$ 盒，第 $l+1$ 盒，...，第 $r$ 盒中的全部酥饼拿出来分享。

出于公平和方便，他希望拿出的酥饼总数是 $36$ 的倍数。

他想要知道有多少种选择区间 $[l,r]$ 的方案，使得 $36\mid\displaystyle\sum_{i=l}^r a_i$。其中 $x\mid y$ 表示 $x$ 整除 $y$，也就是 $y$ 是 $x$ 的倍数。

第一行一个正整数 $n\ (1\le n\le 10^5)$。

接下来一行有 $n$ 个正整数 $a_i\ (1\le a_i\le 10^9)$，分别表示每一盒的酥饼数量。

一行一个整数，表示答案。

样例 1

输入

5
1 35 1 35 1

输出

6

解释

如果选择 $[1,4]$（绿色的区间），里面有 $1+35+1+35=72$ 块酥饼，是 $36$ 的倍数，符合条件。

如果选择 $[3,5]$（红色的区间），里面有 $1+35+1=37$ 块酥饼，不是 $36$ 的倍数，不符合条件。

不难发现，一共有 $\displaystyle\binom n 2$ 中符合条件的区间，其中符合条件的区间为 $[1,2],[1,4],[2,3],[2,5],[3,4],[4,5]$，共有六个符合条件的区间。