Hi , I am interested to solve a problem and I can not find a polynomial solution . How many spanning trees are in a grid graph(N x M)?

It is an array with n elements and d[i] = how many substrings have XOR value i. What is the optimal algorithm for build this dp? substring = a[i1] , a[i2] , ... not contigous.