Firebase Authentication keeps crashing

Question

I'm trying to use Firebase phone authentication but it keeps crashing. It appears it has to do with Google Play Services.

Below are the crash logs.

packageName=com.geek.v
versionName=1.0
throwClassName=com.google.firebase.auth.api.internal.zzah
throwMethodName=zzcy
throwLineNumber=25
exceptionMessage=There was an error while initializing the connection to Google Play Services: java.lang.NoClassDefFoundError: Failed resolution of: Landroid/support/v4/util/ArraySet;
exceptionClassName=java.lang.RuntimeException
stackTrace=
java.lang.RuntimeException: There was an error while initializing the connection to Google Play Services: java.lang.NoClassDefFoundError: Failed resolution of: Landroid/support/v4/util/ArraySet;
    at com.google.firebase.auth.api.internal.zzah.zzcy(Unknown Source)
    at com.google.firebase.auth.api.internal.zzah.zzbq(Unknown Source)
    at com.google.firebase.auth.api.internal.zzah.zzb(Unknown Source)
    at com.google.firebase.auth.api.internal.zzao.zza(Unknown Source)
    at com.google.firebase.auth.FirebaseAuth.zza(Unknown Source)
    at com.google.firebase.auth.PhoneAuthProvider.zza(Unknown Source)
    at com.google.firebase.auth.PhoneAuthProvider.verifyPhoneNumber(Unknown Source)
    at com.geek.v.MainActivity.sendVerificationCode(MainActivity.java:75)
    at com.geek.v.MainActivity.access$1000006(MainActivity.java)
    at com.geek.v.MainActivity$100000000.onClick(MainActivity.java:68)
    at android.view.View.performClick(View.java:6190)
    at android.view.View$PerformClick.run(View.java:23226)
    at android.os.Handler.handleCallback(Handler.java:836)
    at android.os.Handler.dispatchMessage(Handler.java:103)
    at android.os.Looper.loop(Looper.java:203)
    at android.app.ActivityThread.main(ActivityThread.java:6251)
    at java.lang.reflect.Method.invoke(Native Method)
    at com.android.internal.os.ZygoteInit$MethodAndArgsCaller.run(ZygoteInit.java:1073)
    at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:934)```

This is my MainActivity where Firebase authentication is used.

        if (mAuth.getCurrentUser() != null) {
            // already signed in
            Toast.makeText(getBaseContext(), "You have logged in", Toast.LENGTH_LONG).show();
            }

        done.setOnClickListener(new View.OnClickListener() {
            public void onClick(View v) {
                String userNumber = phone_number.getText().toString();
                if(userNumber.isEmpty()) {}
                else {
                    sendVerificationCode(userNumber);
                    }
                    }      
                    });
    }

    private void sendVerificationCode(String mobile) {
       PhoneAuthProvider.getInstance().verifyPhoneNumber(
            "+234" + mobile,
            60,
            TimeUnit.SECONDS,
            this,
            mCallbacks);
            }

    private PhoneAuthProvider.OnVerificationStateChangedCallbacks mCallbacks = new PhoneAuthProvider.OnVerificationStateChangedCallbacks() {
        @Override
        public void onVerificationCompleted(PhoneAuthCredential phoneAuthCredential) {
            //Getting the code sent by SMS
            String code = phoneAuthCredential.getSmsCode();
            //sometime the code is not detected automatically
            //in this case the code will be null
            //so user has to manually enter the code
            if (code != null) {
                progress.setVisibility(View.GONE);
                phone_number.setText(code);
                //verifying the code
                verifyVerificationCode(code);
                }
                }

        @Override
        public void onVerificationFailed(FirebaseException e) {
            progress.setVisibility(View.GONE);
            Toast.makeText(MainActivity.this, e.getMessage(), Toast.LENGTH_LONG).show();
            }

        @Override
        public void onCodeSent(String s, PhoneAuthProvider.ForceResendingToken forceResendingToken) {
            super.onCodeSent(s, forceResendingToken);
            //storing the verification id that is sent to the user
            mVerificationId = s;
            }
            };

    private void verifyVerificationCode(String code) {
        //creating the credential
         PhoneAuthCredential credential = PhoneAuthProvider.getCredential(mVerificationId, code);
        //signing the user
        signInWithPhoneAuthCredential(credential);
        }

    private void signInWithPhoneAuthCredential(PhoneAuthCredential credential) {
        mAuth.signInWithCredential(credential)
            .addOnCompleteListener(MainActivity.this, new OnCompleteListener<AuthResult>() {
                @Override
                public void onComplete(@NonNull Task<AuthResult> task) {
                    if (task.isSuccessful()) {
                        //verification successful we will start the profile activity
                        progress.setVisibility(View.GONE);
                        Toast.makeText(getBaseContext(), "Successful", Toast.LENGTH_LONG).show();
                        } 
                    else {
                        progress.setVisibility(View.GONE);
                        //verification unsuccessful.. display an error message
                        String message = "Something went wrong";
                        if(task.getException() instanceof FirebaseAuthInvalidCredentialsException) {
                            message = "Invalid code entered...";
                            }
                        Toast.makeText(getBaseContext(), message, Toast.LENGTH_LONG).show();
                        }
                        }
                        });
            }


}

app/build.gradle

dependencies {
    api 'com.android.support:design:25.0.1'
    api 'com.google.firebase:firebase-auth:16.0.5'
    api 'com.google.firebase:firebase-core:16.0.6'
    compile fileTree(dir: 'libs', include: ['*.jar'])
}

apply plugin: 'com.google.gms.google-services'