Problem Link 737Div2 C

This is my solution. First, represent the $$$n$$$ numbers in binary. Each number has $$$k$$$ digits, where each digit can be $$$0$$$ or $$$1.$$$ Let $$$a_{i, j}$$$ represent the $$$j$$$th digit (from left to right) of $$$a_i$$$, where $$$a_i$$$ is represented in binary.

Now,

is true if for all $$$1 \le j \le k,$$$

Let's consider the inequality for $$$j = 1,$$$ because others values of $$$j$$$ are similar.

If more than one of $$$a_{i,1} = 0$$$ for $$$1 \le i \le n,$$$ then the left side of the above inequality is going to be zero. This requires the right side of the above inequality to be zero, so an even number of $$$a_{i,1}$$$ should be $$$1$$$.

Also, if all of $$$a_{i,1}=1,$$$ then that is another possible case. This only needs to be considered if $$$n$$$ is odd.

Now, using the above two paragraphs, there are

ways to pick the $$$1$$$st digit for all $$$a_i.$$$

Using the Binomial Theorem on $$$(1+1)^n$$$ and $$$(1-1)^n,$$$ we can show that $$$\sum_{p=0}^{\lfloor n/2 \rfloor} \binom{n}{2p} = 2^{n - 1}.$$$

Thus, the number of ways to pick the $$$1$$$st digit for all $$$a_i$$$ is $$$2^{n - 1} + n\mod 2.$$$ Similarly, this is the number of ways to pick the $$$j$$$th digit for all $$$a_i.$$$

Since there are $$$k$$$ digits total in each of $$$a_i,$$$ the answer is $$$(2^{n - 1} + n \mod 2)^k.$$$

My code describes this approach, and I think it performs this approach correctly. Thus, I believe my approach to the problem is incorrect. Can anyone point out what is wrong?

I have also attached by code in case it is wrong.

Thanks for the help everyone!!

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
 
ll modpow(int x, int n, int m) {
	if (n == 0) return 1 % m;
	long long u = modpow(x, n / 2, m);
	u = (u * u) % m;
	if (n % 2 == 1) u = (u * x) % m;
	return u;
}
 
void solve() {
	int n, k; cin >> n >> k;
	if(k == 0) {
		cout << "1\n";
		return;
	}
	long long ans = 1;
	long long each = (modpow(2, n - 1, MOD1) + n % 2) % MOD1;
	for(int i = 0; i < k; i++) {
		// if n % 2 == 0 don't add anything
		ans *= each;
		ans %= MOD1;
	}
	cout << ans << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t; cin >> t;
	while(t--) {
		solve();
	}
}