Một hôm algorit và bin9638 đang đi chơi thì bị lạc vào một khu rừng tăm tối , đi được một hồi thì gặp người đàn ông , \(2\) người hỏi lối ra của khu rừng thì ông ta nói rằng nếu giải được bài toán này thì cả hai người đều được chỉ lối thoát , còn không thì một trong hai người phải ở lại . Vì tính đoàn kết nên hai người này nhất quyết phải thoát ra ngoài cùng nhau . Hãy giúp hai anh chàng này thoát ra khỏi khu rừng nhé !

Bài toán như sau : Cho một dãy số nguyên \(A\) gồm \(n\) phần tử và một số nguyên \(k\) , hãy chia dãy số thành các dãy con không giao nhau sao cho các dãy con có tổng bằng \(k\) là nhiều nhất .

Ví dụ : Dãy số là { 2 , 1 , 1 , 1 , 1 , 2 } và \(k =\) 4 ;
Chúng ta sẽ chia dãy thành {2,1,1} và {1,1,2} => có hai dãy con có tổng bằng k.

Yêu cầu : Hãy đưa ra số lượng dãy có tổng bằng \(k\) khi chia tối ưu.

Input

• Dòng thứ nhất gồm \(2\) số nguyên \(n\) và \(k\) (\(1 \leq |k| \leq\) \(10^{15}\))
• Dòng tiếp theo là dãy số (\(|A_i|\) \(\leq\) \(10^9\))

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán .

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq\) \(10^2\) , \(|A_i| \leq 10^3\) .
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq\) \(10^3\) , \(|A_i| \leq 10^6\) .
• Subtask \(3\) (\(60\%\) số điểm): \(n \leq\) \(10^6\) , \(|A_i| \leq 10^9\) .

Example

6 4
2 1 1 1 1 2

2

7 3
1 3 2 1 1 1 2

3