Google Play Services has stopped.

I let my phone run out of battery recently and now when I turn it on I keep getting the message "unfortunately, google play service has stopped". It literally appears every second making it impossible to do anything.

I'm trying to factory reset my phone to solve this problem but after clicking it using the power and volume button method it'll load up for a few seconds then put me back into the fastboot menu.

I'm using an HTC One M8

How can I solve this?

Welcome to Android Central! Can you boot into Safe Mode? https://support.t-mobile.com/docs/DOC-10853