Harder to explain look on utube at how to replace hard drive its very easy and u will see where it is underneath.. also if shop did it very unlikely it is in wrong so so I would try what cobalt said and go with checking out bios when u get into it,
or if they fitted it take it back to them and tell them u cant reinstall windows and why they should do it free