First, we will find the relative positions of point \(1\) and point \(i\) for each point \(i=1,2,\ldots,N\). Let point \(1\)’s coordinate be \(0\), and let coordinate \(d\) denote the point \(d\) units of distance away clockwise from coordinate \(0\).

Point \(i\) is \((d_1+d_2+\dots+d_{i-1})\) units away clockwise from point \(1\), so its coordinate \(x_i\) is \(x_i=d_1+d_2+\dots+d_{i-1}\ (\mathrm{mod}\ L)\). By using cumulative sums, we can find \(x_1,x_2,\ldots,x_N\) in a total of \(O(N)\) time.

Three points \(a,b,c\) form a equilateral triangle if and only if these there points divide the circumference equally. For example, if \(x_a<x_b<x_c\), this condition is represented as:

• \(x_b=x_a+L/3\) and \(x_c=x_b+L/3\).

More formally, three points form a equilateral triangles if and only if:

• there exists an integer \(k\ (0\leq k\lt L/3\) such that \(\lbrace x_a,x_b,x_c\rbrace=\lbrace k,k+L/3,k+2L/3\rbrace\).

Therefore, for a frequency array \(\mathrm{cnt}\) of \(x_1,x_2,\dots,x_N\), the answer is \(\displaystyle \sum_{k=0}^{L/3-1} \mathrm{cnt}[k]\times \mathrm{cnt}[k+L/3]\times \mathrm{cnt}[k+2L/3]\).

If \(L\) is indivisible by \(3\), the answer is \(0\).

Sample code (Python)

N, L = map(int, input().split())
if L % 3 != 0:
    print(0)
    exit()
d = list(map(int, input().split()))
x = 0
cnt = [0] * L
for i in range(N):
    if i != 0:
        x += d[i - 1]
    x %= L
    cnt[x] += 1

ans = 0
for i in range(L // 3):
    ans += cnt[i] * cnt[i + L // 3] * cnt[i + 2 * L // 3]
print(ans)