I was unable to solve this question and i want to know what i missed

Given a binary string Q of length <=10^5, find total no of pairs which satisfy following conditions i+j <= X (where X is less than Q) i xor j = X return the answer in Modulo 10^9+7

My approach :- Converted the input to decimal and iterated over lower half of the DP array to find such pairs. Each match increased the count by +2 as i was accounting for both of the possible pairs.

Outcome : TLE on private test cases

The following code is the one i coded earlier and later i realised i don't really need to create an array as i can code the for loop to simply iterate on the imaginary array without overlapping any case but still for reference here is my initial solution

def binaryToDecimal(n): return int(n,2)

def pairCount(n): result = -1 arr = [] for r in range(n+1): arr.append([0 for c in range(n+1)]) for i in range(n+1): for j in range(n+1): temp = i+j if arr[i][j]==0: if temp<=n: if (temp == (int(i)^int(j))): result+=2 arr[i][j] = 1 arr[j][i] = 1

return(result%(1000000009))

n = int(input())

a = binaryToDecimal('1111111111') print(pairCount(a))