Last Updated: 30 Sep, 2025
Great Bitwise Arrays
Hard
You are given three integers: N, M, and K. Your task is to find the number of "great" arrays of length N.
An array A of length X is considered great if for all i from 2 to X, the condition bitcount(A[i-1] & A[i]) = K holds true. The elements A[i] of the array must satisfy 0 <= A[i] < 2^M.
Since the total number of great arrays can be very large, you must return the count modulo 1,000,000,007.
Input Format:
The first line contains an integer N.
The second line contains an integer M.
The third line contains an integer K.
Output Format:
Print a single integer representing the total number of great arrays, modulo 1,000,000,007.
