405553: GYM101992 A Zeros and Ones

Given four integers x, y, M and K. You need to count the number of integers d that satisfy the following rules:

1. The binary representation of d should consist of x ones and y zeroes without leading zeros.
2. d modulo M is greater than or equal to K.

The first line of the input is the number of test cases T. Each test case consists of four integers x, y, M and K, where 1 ≤ M ≤ 10⁹, 1 ≤ x + y ≤ 42, x ≥ 1, y ≥ 0 and 0 ≤ K < M.

For each test case output a single line with the number of integers d that satisfy the rules.

1
2 2 8 2

2