iPhone 5S stuck on 1669 error

I've been using my iPhone 5S (A1457) for about 3 months on iOS 7.0.4. Then once I saw "searching" sign on the top of the screen (instead of carrier name). I took out the sim slot and nothing happened: "searching" sign was still displayed. I tried rebooting - didn't fix the issue. After that I decided to restore through iTunes, but then I got error 1669 and "connect to itunes" screen. What should I do? I need my phone as fast as possible. Help, please!