Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8820

Jo'natishlar soni: 714406

Muhokama yozuvlari: 4541

Yangiliklar soni: 97

Yangiliklar izohlari: 1174


So'ngi izohlar

781. Sum of array elements
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

You are given integers a1, ..., an  and an integer number s. Your task is to determine how many consecutive non-empty sets of integers al, al + 1, ..., ar (l ≤ r) have the sum al + al + 1 + ... + ar = s.

Input

The first line contains two integers separated by space: n and s (1 ≤ n ≤ 105,  - 1014 ≤ s ≤ 1014). The second line contains n integers separated by space: ai ( - 109 ≤ ai ≤ 109).

Output

Output the only integer — the number of consecutive non-empty sets of integers which have the sum s.

Samples

Input

Output

1

5 2
-1 1 2 -1 1

5

2

6 3
3 -2 1 -1 1 2

3

 

Tayyorladi: Azat Yusupov
Text from: codeforces.ru
Mening urinishlarim(0) Muhokama (0) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(60) Barcha urinishlar(124)