Số nguyên \(p\) được gọi là hoàn hảo nếu \(p > 0\) và tổng tất cả các ước của \(p\) bằng \(2 \cdot p\). Ví dụ, số \(6\) là số hoàn hảo vì tổng các ước của \(6\) là \(1 + 2 + 3 + 6 = 12 = 2 \cdot 6\).

Yêu cầu: Cho dãy số nguyên \(a_1, a_2, \dots, a_n\) và số \(w\), hãy đếm số cách chọn một đoạn số mà tổng các phần tử thuộc đoạn là số hoàn hảo không vượt quá \(w\), cụ thể cần đếm số cách chọn hai chỉ số \(L, R\) thỏa mãn: \(1 \le L \le R \le n\) và \(a_L + a_{L+1} + \dots + a_R\) là số hoàn hảo không vượt quá \(w\).

Input

• Dòng đầu gồm hai số nguyên dương \(n, w\) (\(n \le 10^5; w \le 10^{15}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9; 1 \le i \le n\)).

Output

• Gồm một dòng chứa một số là số cách chọn thỏa mãn.

Example

3 6
6 6 -6

3

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 1000; w \le 6\).
• Subtask \(2\) (\(30\%\) số điểm): \(w \le 6\).
• Subtask \(3\) (\(30\%\) số điểm): \(w \le 10^6\).
• Subtask \(4\) (\(10\%\) số điểm): Không có ràng buộc nào thêm.