Android 7.0 introduces a new signature scheme, V2.
The V2 scheme signs the entire APK rather than just the JAR, as is done in the V1 scheme. If you sign with only V2, and attempt to install on a pre-7.0 target, you'll get this error since the JARs themselves are not signed and the pre-7.0 PackageManager cannot detect the presence of the V2 APK signature.
To be compatible with all target systems, make sure the APK is signed with both schemes by checking both signature version boxes in Android Studio's Generate Signed APK dialog as shown here:
For maximum compatibility, sign applications with all schemes, first with v1, then v2, and then v3. Android 7.0+ and newer devices install apps signed with v2+ schemes more quickly than those signed only with v1 scheme. Older Android platforms ignore v2+ signatures and thus need apps to contain v1 signatures.