human
I found an interesting problem on https://leetcode.com/problems/binary-subarrays-with-sum/:
In an array A of 0s and 1s, how many non-empty subarrays have sum S?
 
Example 1:
Input: A = [1,0,1,0,1], S = 2
Output: 4
Explanation: 
The 4 subarrays are bolded below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]

 
Note:

A.length <= 30000
0 <= S <= A.length
A[i] is either 0 or 1.

I tried it in Python, but could not do it. Can you solve it?
assistant
#Here is the Python code you requested.

class Solution:
    def numSubarraysWithSum(self, A: List[int], S: int) -> int:
        n = len(A)
        prefix = [0 for _ in range(n+1)]
        for i in range(n):
            prefix[i+1] = prefix[i] + A[i]
        
        def at_most_k(k: int) -> int:
            begin, end = 0, 1
            cnt = 0
            while end < n+1:
                while begin < end and prefix[end] - prefix[begin] > k:
                    begin += 1
                cnt += end - begin
                end += 1
            return cnt

        return at_most_k(S) - at_most_k(S-1)