M31 has a giant stream of stars extending far to the south and a great deal of other tidal debris in its halo, much of which is thought to be directly associated with the southern stream. We model this structure by means of Bayesian sampling of parameter space, where each sample uses an N-body simulation of a satellite disrupting in M31's potential. We combine constraints on stellar surface densities from the Isaac Newton Telescope survey of M31 with kinematic data and photometric distances. This combination of data tightly constrains the model, indicating a stellar mass at last pericentric passage of log10 (M s /M) = 9.5 ± 0.1, comparable to the Large Magellanic Cloud. Any existing remnant of the satellite is expected to lie in the Northeast (NE) Shelf region beside M31's disc, at velocities more negative than M31's disc in this region. This rules out the prominent satellites M32 or NGC 205 as the progenitor, but an overdensity recently discovered in M31's NE disc sits at the edge of the progenitor locations found in the model. M31's virial mass is constrained in this model to be log10 M 200 = 12.3 ± 0.1, alleviating the previous tension between observational virial mass estimates and expectations from the general galactic population and the timing argument. The techniques used in this paper, which should be more generally applicable, are a powerful method of extracting physical inferences from observational data on tidal debris structures.