In this Letter, we present, for the first time, to the best of our knowledge, the modulation instability (MI) gain spectrum of waveguides with an arbitrary frequency-dependent nonlinear coefficient ensuring strict energy and photon-number conservation of the parametric process. This is achieved by starting from a linear stability analysis of the recently introduced photon-conserving nonlinear Schrödinger equation. The derived MI gain is shown to predict some unique features, such as a nonzero gain extending beyond a zero-nonlinearity wavelength and a complex structure of the MI gain spectrum. Analytical results are shown to be in excellent agreement with numerical simulations.