Concatenating two binary numbers of size 4 abcd and efgh to abcdefgh is the same as abcd*2^4 + efgh. Same reason why 27 = 2*10 + 7 or 1234 = 12*10^2 + 34.

Your solution doesn't work, because pow(2,x - i) will return a double.

You convert it implicitly into a long long. But for some big x and small i, the value of pow(2,x - i) will be too big for a long long, and therefore you will get an integer overflow, and you end up with a random number, possible negative.

Second, doubles only have a certain amount of accuracy. So computing the power and converting it back will almost always end up with an inaccurate result.

If you want to compute big exponents mod some number, take a look at this algorithm: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation

Each character of the original program is replaced by a binary code of length 4. This means that when you append code for one character, the rest of the code is shifted right by 4 binary digits, which is the same as multiplied by 2⁴ = 16.

Storing power of 2 in long long overflows; you have to take modulo during the power calculation, not in the end (https://ideone.com/Kq9tBI)