Ông tổ Turing vừa tạo ra một chiếc máy dùng để giải mã mật mã Enigma của lũ phát xít Đức. Nó là một quả bom. Vâng, chỉ là một quả Bomb(e). Với mỗi mật mã của phát xít Đức mà chúng ta trộm được, chỉ cần ném quả bom này là chúng ta sẽ giải mã và đọc được thông điệp.
Tuy nhiên, có lẽ địch biết điều này, nên đôi khi chúng gửi thông tin nhiễu cho phe Đồng minh. Vì vậy ông Turing phải tìm thuật toán tính độ tin cậy thông điệp.
Yay, ông tổ nghề của chúng ta đã tìm ra rồi! Mỗi thông điệp đều có dạng là một xâu nhị phân S (mà sau đó sẽ được dịch sang bảng mã của quân Đức) chứa hai ký tự '0' và '1'. Ông tính độ tin cậy của S bằng cách đếm số lượng xâu con có chứa ít nhất một kí tự '1'.
Nói cách khác, độ tin cậy của xâu S độ dài N là số cặp (l, r) sao cho 1 <= l <= r <= N, sao cho có ít nhất một trong các kí tự Sl, Sl + 1, Sl + 2, ..., Sr là kí tự '1'.
Sau khi đánh bại quân phát xít Đức, Turing đố các cộng sự mình một bài toán: cho một xâu nhị phân S có độ dài L bất kỳ có đúng K ký tự '1', hỏi độ tin cậy lớn nhất là bao nhiêu?
Tất nhiên, các cộng sự của Turing không giỏi như ông, nên các bạn hãy giúp họ nhé!
INPUT: Gồm một dòng duy nhất lần lượt gồm hai số L, K.
OUTPUT: Độ tin cậy lớn nhất của một xâu nhị phân độ dài L có K kí tự '1'
Bộ test gồm:
Subtask 1: n <= 20
Subtask 2: n <= 314159265
| INPUT | OUTPUT |
| 3 2 |
5 |
Giải thích: Xâu "101" có 5 xâu con thỏa mãn: (1, 1) (1, 2) (1, 3) (2, 3) (3, 3). Đây là xâu có độ tin cậy lớn nhất trong các xâu thỏa điều kiện đầu vào.