Count Collisions of Monkeys on a Polygon

Count the number of assignments where each of n monkeys independently steps to a neighboring vertex (2^n total) that produce at least one collision; the key is combinatorics: only the two uniform directions are collision-free, so the answer is (2^n − 2) mod 1e9+7, computed with fast modular exponentiation for large n.