I am working on the FCM integration but getting the java.lang.ClassNotFoundException: Didn't find class "service.MyFirebaseMessagingService" on path: DexPathList[[zip file "/data/app/com.rk.servicepractise-2/base.apk"],nativeLibraryDirectories=[/vendor/lib64, /system/lib64]] 
I have searched it about but did not get the proper solution yet,Please check my code below and let me know where am i doing wrong?
Please check my classes  and manifest file with gradle, Please  help me to short out from this problem.
My first class that is the MyFirebaseInstanceIDService which extends FirebaseInstanceIdService class
public class MyFirebaseInstanceIDService extends FirebaseInstanceIdService {
    private static final String TAG = "MyFirebaseIIDService";
    @Override
    public void onTokenRefresh() {
        //Getting registration token
        String refreshedToken = FirebaseInstanceId.getInstance().getToken();
        //Displaying token on logcat
        Log.d(TAG, "Refreshed token: " + refreshedToken);
    }
    private void sendRegistrationToServer(String token) {
        //You can implement this method to store the token on your server
        //Not required for current project
    }
}
And one more class for the Fcm that extends FirebaseMessagingService class which are as follow:-
public class MyFirebaseMessagingService extends FirebaseMessagingService {
    private static final String TAG = "MyFirebaseMsgService";
    @Override
    public void onMessageReceived(RemoteMessage remoteMessage) {
        //Displaying data in log
        //It is optional
        Log.d(TAG, "From: " + remoteMessage.getFrom());
        Log.d(TAG, "Notification Message Body: " + remoteMessage.getNotification().getBody());
        //Calling method to generate notification
        sendNotification(remoteMessage.getNotification().getBody());
    }
    //This method is only generating push notification
    //It is same as we did in earlier posts
    private void sendNotification(String messageBody) {
        Intent intent = new Intent(this, MainActivity.class);
        intent.addFlags(Intent.FLAG_ACTIVITY_CLEAR_TOP);
        PendingIntent pendingIntent = PendingIntent.getActivity(this, 0, intent,
                PendingIntent.FLAG_ONE_SHOT);
        Uri defaultSoundUri= RingtoneManager.getDefaultUri(RingtoneManager.TYPE_NOTIFICATION);
        NotificationCompat.Builder notificationBuilder = new NotificationCompat.Builder(this)
                .setSmallIcon(R.mipmap.ic_launcher)
                .setContentTitle("Firebase Push Notification")
                .setContentText(messageBody)
                .setAutoCancel(true)
                .setSound(defaultSoundUri)
                .setContentIntent(pendingIntent);
        NotificationManager notificationManager =
                (NotificationManager) getSystemService(Context.NOTIFICATION_SERVICE);
        notificationManager.notify(0, notificationBuilder.build());
    }
}
And here below is my Manifest file entry for this Fcm
<application>
.
.
.
.
  <service
        android:name="com.rk.servicepractise.service.MyFirebaseMessagingService">
        <intent-filter>
            <action android:name="com.google.firebase.MESSAGING_EVENT"/>
        </intent-filter>
    </service>
    <service
        android:name="com.rk.servicepractise.service.MyFirebaseInstanceIDService">
        <intent-filter>
            <action android:name="com.google.firebase.INSTANCE_ID_EVENT"/>
        </intent-filter>
    </service>
    </application>
And the gradle which i am using for it as follow Module:app:-
apply plugin: 'com.android.application'
android {
.
.
.
.
.
}
dependencies {
    compile fileTree(include: ['*.jar'], dir: 'libs')
    testCompile 'junit:junit:4.12'
    compile 'com.android.support:appcompat-v7:23.1.1'
    compile 'com.android.support:design:23.1.1'
    compile 'com.google.firebase:firebase-messaging:9.8.0'
}
apply plugin: 'com.google.gms.google-services'
build.gradle foe the Project:ProjectName
buildscript {
    repositories {
        jcenter()
    }
    dependencies {
        classpath 'com.android.tools.build:gradle:1.5.0'
        classpath 'com.google.gms:google-services:3.0.0'
        // NOTE: Do not place your application dependencies here; they belong
        // in the individual module build.gradle files
    }
}
And the below is the Exception which i am getting:-
                                                           java.lang.RuntimeException: Unable to instantiate service service.MyFirebaseInstanceIDService: java.lang.ClassNotFoundException: Didn't find class "service.MyFirebaseInstanceIDService" on path: DexPathList[[zip file "/data/app/com.rk.servicepractise-1/base.apk"],nativeLibraryDirectories=[/vendor/lib64, /system/lib64]]
                                                                    at android.app.ActivityThread.handleCreateService(ActivityThread.java:2779)
                                                                    at android.app.ActivityThread.access$1900(ActivityThread.java:154)
                                                                    at android.app.ActivityThread$H.handleMessage(ActivityThread.java:1404)
                                                                    at android.os.Handler.dispatchMessage(Handler.java:102)
                                                                    at android.os.Looper.loop(Looper.java:135)
                                                                    at android.app.ActivityThread.main(ActivityThread.java:5292)
                                                                    at java.lang.reflect.Method.invoke(Native Method)
                                                                    at java.lang.reflect.Method.invoke(Method.java:372)
                                                                    at com.android.internal.os.ZygoteInit$MethodAndArgsCaller.run(ZygoteInit.java:904)
                                                                    at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:699)
                                                                 Caused by: java.lang.ClassNotFoundException: Didn't find class "service.MyFirebaseInstanceIDService" on path: DexPathList[[zip file "/data/app/com.rk.servicepractise-1/base.apk"],nativeLibraryDirectories=[/vendor/lib64, /system/lib64]]
                                                                    at dalvik.system.BaseDexClassLoader.findClass(BaseDexClassLoader.java:56)
                                                                    at java.lang.ClassLoader.loadClass(ClassLoader.java:511)
                                                                    at java.lang.ClassLoader.loadClass(ClassLoader.java:469)
                                                                    at android.app.ActivityThread.handleCreateService(ActivityThread.java:2776)
                                                                    at android.app.ActivityThread.access$1900(ActivityThread.java:154) 
                                                                    at android.app.ActivityThread$H.handleMessage(ActivityThread.java:1404) 
                                                                    at android.os.Handler.dispatchMessage(Handler.java:102) 
                                                                    at android.os.Looper.loop(Looper.java:135) 
                                                                    at android.app.ActivityThread.main(ActivityThread.java:5292) 
                                                                    at java.lang.reflect.Method.invoke(Native Method) 
                                                                    at java.lang.reflect.Method.invoke(Method.java:372) 
                                                                    at com.android.internal.os.ZygoteInit$MethodAndArgsCaller.run(ZygoteInit.java:904) 
                                                                    at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:699) 
                                                                    Suppressed: java.lang.ClassNotFoundException: service.MyFirebaseInstanceIDService
                                                                    at java.lang.Class.classForName(Native Method)
                                                                    at java.lang.BootClassLoader.findClass(ClassLoader.java:781)
                                                                    at java.lang.BootClassLoader.loadClass(ClassLoader.java:841)
                                                                    at java.lang.ClassLoader.loadClass(ClassLoader.java:504)
EDITED Please follow this link whenever u become stuck in the same problem thanks @Marcin Orlowski ...Link:-Click here