And after the procedure, I see that all my contacts has been disappeared
from the phone :-(
(and of cource - nothing appeared on my account at provider's service page)
How can I restore them?
They were saved in my phone memory (not SIM, not FLASH).
If you do not have some other backup made to a memory card or a PC, then in all likelihood the contacts are permanently gone.
If you immediately turn off the phone and do not use it at all, then perhaps a data recovery service like http://www.ibas.com/ might be able to help recovering phone memory content, if it is still there, but it will be costly and without any guarantees of success.