Modulo-density of binary numbers with fixed digits

Question

Let $var \subseteq \{1,...,n \}$. Let $a=|var|$. Let $p > 2$ be a prime number. Let $0 \leq q < p$ be a fixed remainder modulo $p$.

$$M = \{w \in \{0,1\}^a : \text{number}(\widehat{w}) \equiv q \mod p\}$$

Where $\widehat{w} = \widehat{w_1}\cdots \widehat{w_n}$ and $$ \widehat{w_i} = \begin{cases} w_i & \text{if } i \in var \\ 0 & \text{else} \end{cases} $$

$\widehat{w}$ can be understood as a binary word that is filled with 0 to be stretched to the length of $n$ at exactly those places $i$ where $i \not\in var$.

My question now is whether $|M| \geq \frac{2^{a}}{p} \pm 1$ (or any similar lower bound) can be proven.

1. I already now that this is true for $var = {i,...,n}$ as then all $\text{number}(\widehat{w})$ are just the numbers from $0$ to $2^{n-i}$ and as such, every $p$-th number must be $q \mod p$.

2. Similary, I already now that this is true for $var = {1,...,j}$ as those $\text{number}(\widehat{w})$ are just the numbers above multiplied with some factor $2^k$. As such, every increase in $w$ means an increase of $2^k$ in $\text{number}(\widehat{w})$. Again, every $p$-th number must be $q \mod p$.

The problem lies within $var$ where there are fixed zeros in $\widehat{w}$ between some ones. Now, an increase in $w$ can mean any size of increase in $\widehat{w}$.

The reasoning why I think it's true is because I have tested it for the first few prime numbers and looked at the distribution of the remainders for every possible $\widehat{w}$ given some $var$.

Things I have tried:

• Fixing some vector $v \equiv q \mod p$ and flipping a few bits to see how the remainder changes. Result: one flip is okay (meaning the remainder can no longer be q), after two flips the remainder may already be $q$ again. The resulting neighborhood of vectors for which the remainder isn't $q$ isn't large enough to make the proof work.
• Moving the zeros up to the front. When moving a zero to the front of a binary number (101001 => 010101). I couldn't see a systemic difference in $q$ resulting from this change.
• Seeing zeros in the middle as a sum of words that are like 1. and 2. the problem here is: words like $1010101$ are a large sum and the lower bounds from 1. and 2. can't be carried over in a meaningful way.

I suspect this has already been proven somewhere but my math-vocabulary isn't strong enough to search for it. If any of you see similarities to existing (solved or disproved) problems, I'd be interested in that as well). Maybe something regarding hashing or cyclic group theory?