Sometimes scenarios like this happen.  I will make the assumption that it was an honest mistake by the contractor and they would not have agreed to the modification deobligating funds if they knew/realized they hadn't been paid yet.  I will also make the assumption that the contractor completed the work successfully and it was accepted by the government.

My advice is to pay the invoice; see FAR 1.602-2(b).  If my assumptions above are accurate, it is quite dubious the government would prevail should the contractor choose to file a claim.  Furthermore, a claim under the disputes act would require a contracting officers final decision.  Most agencies require the contracting officer's final decision to be reviewed by legal... I seriously doubt (again if my assumptions are accurate) any contract attorney would approve of such a contracting officer's final decision denying payment in this case.

Because of the Time Statute 31 U.S.C. § 1502 you will need to use FY19 funds. Your finance office should know the procedures and forms you will need to follow/fill out to request an Obligation Adjustment Requirement.  There is a very, very good chance your agency still has FY19 funds.  While these can't be used for new requirements (they don't expire for another 4 years) they can be used for adjustments on work during FY19,  specifically for the purposes that your scenario represents.