Подсчитайте массивы N-длины, состоящие из элементов, не превышающих 2 ^ K - 1, имеющих максимальную сумму и побитовое И, равное 0

Даны два целых числа N и K. Задача состоит в том, чтобы найти количество массивов длины N , удовлетворяющих следующим условиям:

• Сумма элементов массива максимально возможная.
• Для каждого возможного значения i ( 1 ≤ i ≤ N ) i ^-й элемент должен лежать между 0 и 2 ^K – 1 .
• Кроме того, побитовое И всех элементов массива должно быть равно 0.

Примечание. Поскольку ответ может быть большим, выведите ответ по модулю 10^9 + 7 .

Примеры :

Input : N=2 K =2
Output : 4
Explanation : The required arrays are ( {1, 2}, {2, 1}, {0, 3}, {3, 0} )

Input : N=1 K =1
Output : 1

Подход: Идея состоит в том, чтобы заметить, что если все биты всех элементов в массиве равны 1 , то побитовое И всех элементов не будет равно 0 , хотя сумма будет максимальной. Таким образом, для каждого бита переверните 1 на 0 в каждом бите хотя бы в одном из элементов, чтобы сделать побитовое И равным 0 и в то же время сохранить максимальную сумму. Итак, для каждого бита выберите ровно один элемент и переверните бит там. Поскольку есть K бит и N элементов, ответ будет просто N^K . Выполните следующие шаги, чтобы решить проблему:

• Определите функцию power(long long x, long long y, int p) и выполните следующие задачи:
  • Инициализируйте переменную res как 1 , чтобы сохранить результат.
  • Обновите значение x как x%p.
  • Если x равно 0, то вернуть 0.
  • Повторяйте цикл while, пока y не станет больше 0 , и выполните следующие задачи.
    • Если y нечетное, установите значение res как (res*x)%p.
    • Разделите у на 2.
    • Установите значение x как (x*x)%p.
• Инициализируйте переменную mod как 1e9+7.
• Инициализируйте переменную an как значение, возвращаемое функцией power(N, K, mod).
• После выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (log (K))
Вспомогательное пространство: O(1)