During Codeforces Round 934 (Div. 2) I submitted problem D hoping to get the green AC but unfortunately got the red WA (submission 251770538). I spent the rest of the time in the contest trying to figure out the problem in vain. After the contest, I checked the accepted solutions and found that they were exactly like mine which made me more confused.

I stress-tested my solution using a brute-force approach during the contest and using AC solutions after the contest time but couldn't find a single test case. Even after **a million random test cases**, my solution is still steadfast. I know that a few hundred test cases are enough.

My implementation of string hashing is inspired by Usaco.guide, which uses random bases and a fixed modulus (`1LL << 61) -1`

). I used multiple bases to make sure no collisions happen, but this also didn't help.

**Usaco.guide string hashing implementation**

Unfortunately, I couldn't get AC during the contest but now I'm curious about this weird behavior of string hashing. Why using many random bases doesn't help and the solution is to use a prime modulus (i.e. $$$10^9 + 7$$$)?

Now the situation is more complex, I tried to submit a solution (submission 252010026) with only one base and $$$10^9 + 7$$$ as a modulus and got AC. Isn't the collision probability high for such a case?

Another thing to note is the inability to use GNU C++20 compiler caused all of this chaos because I couldn't use `__int128`

and `(1LL << 61) - 1`

as a modulus which I think will get AC.