Problem Statement

You find yourself in front of a magical door locked by an intricate grid mechanism of size N × M. Some cells of the grid are mag ically broken and cannot be drawn upon. To unlock the door , you must draw a single closed loop on the grid. Formally, the loop is a set of connections between orthogonally adjacent intact cells (a connection joins two cells sharing an edge — up, down, left, or right) such that: every non-broken cell is used by exactly two connections of the loop, and the connections form one single cycle that visits every non-broken cell exactly once (it does not split into two or more separate loops, and it touches no broken cell). Given the configuration of the grid, determine the total number of distinct valid loops. What counts as distinct: A loop is defined uniquely by its set of connections. Direction of travel and choice of starting cell do not matter — for example, traversing a loop clockwise versus counter-clockwise is the same loop, and starting at a different cell