Samsung galaxy s4 needs unlock code but provider says they dont have them???

[nanypants]

My samsung galaxy s4 model sgh 1337 was stolen. When I recovered it, there was a prompt for a network unlock code, but my provider (a very small local service provider) said that they dont use unlock codes, and that this is a hardware problem. Is there anything that I can do? I tried factory resetting...