Phone Lost contacts in factory reset

I did a factory reset to my Samsung Galaxy S II (GT-I1900) as I was facing some performance issues. Unfortunately, did not take a backup & lost all my contacts (almost 1100). Now the issue is that I'm left without any contacts in my phone. Can someone please help me recovering lost contacts?

Few details -

The device is rooted & running on Cynogenmod 10.1.3
Tried almost every data recovery software available on the internet
Have an idea of querying the android contacts database using adb, but require some help with this.

Any assistance would help a lot.