Problem 46761. Inverse Number Theoretic Transform (iNTT)

I had to cheat to pass this problem but have few thoughts with AI's help.

**NTT definition**: The inverse transform is not just “run the forward transform backwards.” You need to apply the correct twiddle factors (powers of the inverse root of unity) and scale by the modular inverse of `n`.
**Primitive roots matter**: A valid primitive n‑th root of unity modulo `p` is the foundation. If the wrong generator is chosen, the transform will not invert correctly.

**Normalization conventions**: Some definitions put the `1/n` factor in the forward transform, others in the inverse.

**Don’t assume n is a power of two**: A general O(n²) definition works for all `n`.

**Use modular arithmetic everywhere**:

Compute with extended Euclidean algorithm or MATLAB’s `gcd`. You’ll need both `n⁻¹ mod p` and `w⁻¹ mod p`.