def first_index_k_ones_right(qstr, k, P):
    """
    For a binary string qstr, return the first index of q with k (mod P) ones to the right.
    Return: index in [0, qstr.length]
    """
    num_ones_right = 0
    for j in range(qstr.length, -1, -1):
        if (num_ones_right - k) % P == 0:
            return j
        if j == 0: 
            raise Exception("No valid position found")
        if qstr[j-1] == 1:
            num_ones_right += 1