I am sure which industry you are working for ? I can understand that any one loosing their job in fine morning is a disaster, however, look at the positive side that it has come early rather than after 6 months.

Since the terms of employment also needs to be worked out accordingly more than the terms & conditions mentioned in the offer letter. So, know your rights first before proceeding further.

Check out whom does the CEO reports to. You may approach him / her for a solution.

Negotiate with the CEO that you will try to move out once you get another offer till that time, you need to be on the job. This is another solution.

Do speak to your ealier boss and try joining back...possible provided you are in good terms with him / her. In one of my replies, I remember saying that employees join organisation but only to leave their bosses.

All the best !

Regards