seuOJ9173 - 酥饼

三只猪在西安旅游两天，带回来了一箱葡萄，一块木板，一个奶龙手办，两个 fufu，和许多盒酥饼！在程序设计课上，他们决定把其中一些酥饼分给班上的 $36$ 名同学。

$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)$ ，分别表示每一盒的酥饼数量。

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

5
1 35 1 35 1

如果选择 $[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]$ ，共有六个符合条件的区间。