For astring of n bits x1, x2, x3, …, xn, theadjacent bit count of the string isgiven by fun(x) = x1*x2 + x2*x3 + x3*x 4 + … + xn-1*x n
which counts the number of times a 1 bit is adjacent to another 1 bit. Forexample: <o:p></o:p>
Fun(011101101) = 3 <o:p></o:p>
Fun(111101101) = 4 <o:p></o:p>
Fun (010101010) = 0 <o:p></o:p>
Write a program which takes asinput integers n and p and returns the number of bit stringsx of n bits (out of 2ⁿ) that satisfy Fun(x)= p. <o:p></o:p>
Forexample, for 5 bit strings, there are 6 ways of getting fun(x) = 2: <o:p></o:p>
11100,01110, 00111, 10111, 11101, 11011<o:p></o:p>