Hello Codeforces!

Recently I've been trying out a problem in which i have reduced to the following problem:

"implement a modint (where mod = 1e9, similar to the last 9 digits of a number in decimal representation) data structure that supports these basic arithmetic operations: addition, subtraction, multiplication, and division by 2. it is guaranteed that the number is always an integer before and after any of these operations (or in other words, when division by 2 is required, the number is even."

My idea is to represent an integer as 1e9 * (2^k * odd number) + m, but this approach ran into a roadblock when i realised adding/subtracting isnt possible.

Any suggestions/edits to this approach or an entirely different approach? Thanks in advance