Before ELROD, WILLETT, and ENGELHARDT, Circuit Judges. DON R. WILLETT, Circuit Judge: This is the third time this case has reached us.[1] Last time we remanded to the district court so it could consider whether, in light of recent developments, Plaintiffs (collectively Franciscan Alliance) should have been granted a permanent injunction, and not just vacatur of the challenged regulation. On remand, the district court granted Franciscan Alliance’s motion, permanently enjoining the United States Department of Health and Human Services (HHS) from requiring Franciscan Alliance to perform gender-reassignment surgeries or abortions in violation of its sincerely held religious beliefs. HHS and the Intervenor Defendants—the American Civil Liberties Union of Texas, and River City Gender Alliance (collectively ACLU)— argue that the permanent injunction was improper. They contend that Franciscan Alliance’s claims are moot, it was improper to award relief not requested in the complaint, and Franciscan Alliance failed to show it would be irreparably harmed absent an injunction. While we agree with Appellants that we must DISMISS Franciscan Alliance’s APA claim as moot, we AFFIRM the district court’s judgment in all other respects. I Section 1557 of the Patient Protection and Affordable Care Act prohibits health care programs that receive federal funds from discriminating against patients on the basis of sex.[2] Section 1557 incorporates Title IX’s definition of prohibited sex discrimination.[3] The Secretary of HHS has authority to issue regulations to implement Section 1557.[4] In May 2016, HHS issued a rule interpreting Section 1557′s prohibition of “discrimination on the basis of sex.”[5] It defined sex discrimination to include discrimination on the basis of “termination of pregnancy” and “gender identity.”[6] Franciscan Alliance claimed the rule violated the Administrative Procedure Act (APA) by defining “sex discrimination” inconsistently with Title IX. Franciscan Alliance also claimed that the rule violated the Religious Freedom Restoration Act (RFRA) by forcing it to perform abortions and gender-reassignment surgeries inconsistent with its sincerely held religious beliefs. The district court issued a nationwide preliminary injunction barring enforcement of the challenged parts of the 2016 Rule. The case was stayed to give HHS time to reconsider the 2016 Rule. Before HHS had completed its review, the parties jointly moved to lift the stay, which the district court granted. The district court then granted Franciscan Alliance’s motion for summary judgment and vacated the offending provisions of the 2016 Rule. But it declined to issue an injunction because it found there was no indication that, if the rule was vacated, HHS would bring an enforcement action against Franciscan Alliance. Franciscan Alliance timely appealed the denial of permanent injunctive relief. Shortly thereafter, HHS finalized a new rule implementing Section 1557 (the “2020 Rule”).[7] The 2020 Rule adopted Title IX’s religious exemption and repealed the 2016 Rule’s definition of sex discrimination.[8] But HHS declined to replace it with a new definition, reasoning that the Supreme Court’s impending decision in Bostock would “likely have ramifications for the definition of ‘on the basis of sex’ under Title IX.”[9] Just three days after HHS issued the 2020 Rule, the Supreme Court decided Bostock, holding that Title VII’s prohibition of discrimination “because of” sex made it unlawful to terminate employees for being homosexual or transgender.[10] Bostock triggered multiple lawsuits challenging the 2020 Rule. Most relevant here, two courts entered nationwide injunctions preventing much of the 2020 Rule from going into effect, effectively reinstating portions of the 2016 Rule (the Whitman and Whitman-Walker opinions).[11] Both courts acknowledged they had no power to undo the district court’s vacatur in this case.[12] But in effect they did just that. While those courts did not directly resurrect the 2016 Rule’s prohibition on “gender identity” discrimination, they did reanimate the rule’s “sex-stereotyping” prohibition.[13] Both courts further reasoned that, in light of Bostock, sex-stereotyping discrimination encompasses gender identity discrimination.[14] Whitman-Walker also enjoined the 2020 Rule’s incorporation of Title IX’s religious exemption,[15] even though the district court here held that the 2016 Rule was unlawful for not providing such an exemption. Also while Franciscan Alliance’s appeal was pending, President Biden issued an executive order declaring that his administration would apply Bostock‘s interpretation of Title VII to other statutes prohibiting sex discrimination, including Title IX.[16] He instructed each agency to consider whether new actions are necessary to implement Bostock‘s definition of sex discrimination.[17] HHS is in the process of reconsidering the 2020 Rule. We held oral argument on March 2, 2021. We remanded the case to the district court because “the legal landscape ha[d] shifted significantly” since the district court denied injunctive relief.[18] The 2020 Rule, the Bostock decision, the Walker and Whitman-Walker injunctions, and the new administration’s interpretation of Section 1557 all occurred after the district court issued its order. While the case was back with the district court, HHS issued a “Notification of Interpretation and Enforcement” (the 2021 Interpretation).[19] The 2021 Interpretation stated that in light of Bostock, HHS would enforce Section 1557 to prohibit “discrimination on the basis of gender identity.”[20] It also encouraged members of the public to file complaints with HHS if they believed the rule had been violated.[21] After receiving supplemental briefing, the district court ruled on Franciscan Alliance’s motion for a permanent injunction. The district court rejected HHS’s argument that the 2020 Rule rendered the case moot, found that Franciscan Alliance’s complaint had challenged Section 1557 in addition to the 2016 Rule, and concluded that Rule 54(c) authorized the court to issue the injunction Franciscan Alliance now sought. The district court also concluded that subsequent events showed that partial vacatur of the 2016 Rule was insufficient to remedy the RFRA violation. Finding that Franciscan Alliance had met the requirements for a permanent injunction, the district court enjoined HHS “from interpreting or enforcing Section 1557 . . . or any implementing regulations thereto” against Franciscan Alliance “in a manner that would require [it] to perform” or insure gender-reassignment surgeries or abortions. In November 2021, HHS noticed this appeal. That same month, it withdrew the appeal in Walker and Whitman-Walker, leaving in place the injunctions reinstating parts of the 2016 Rule. Two additional developments occurred while this appeal was pending. In March 2022, HHS issued a “Notice and Guidance on Gender Affirming Care” (the “2022 Notice”).[22] The 2022 Notice states that “[a]ttempts to restrict” gender-reassignment surgeries are “dangerous” and “covered entities restricting an individual’s ability to receive . . . gender-affirming care . . . likely violates Section 1557.”[23] The 2022 Notice also said that HHS “is investigating and, where appropriate, enforcing Section 1557″ in “cases involving discrimination on the basis of . . . gender identity.”[24] And on August 4, 2022, HHS filed a Notice of Proposed Rulemaking (the 2022 NPRM). This proposed rule, if adopted, would reinstate much the same approach as the 2016 Rule by likewise interpreting Section 1557 to require that hospitals perform gender-reassignment surgeries and abortions.[25] II Appellants’ arguments boil down to three overarching issues. First, is the case moot? Second, did the district court err in granting injunctive relief against Section 1557 and all future agency action? And third, did the district court err in finding that Franciscan Alliance demonstrated irreparable harm? We agree with Appellants’ mootness argument in part but hold that the district court did not err on the remaining two issues. A HHS argues that any challenge to the 2016 Rule is now moot because the district court already vacated the parts of the rule that violated the APA, and because the 2020 Rule rescinded the 2016 Rule. While the parties treat the mootness of Franciscan Alliance’s APA and RFRA claims interchangeably, they should be analyzed separately because an APA claim challenges a particular regulation, while a RFRA claim challenges burdens placed on religious conduct. Appellants are right that the APA claim is moot.[26] When a challenged rule is replaced with a new rule, the case is moot so long as the change gives “the precise relief that petitioners requested.”[27] The change will not moot the case if the “government repeals the challenged action and replaces it with something substantially similar.”[28] The 2020 Rule gave Franciscan Alliance the remedy an APA violation called for—vacatur of the 2016 Rule’s prohibition of discrimination on the basis of “termination of pregnancy” and “gender identity.” Franciscan Alliance’s APA claim sought nothing more. Nor could it have. Vacatur is the only statutorily prescribed remedy for a successful APA challenge to a regulation.[29] True, the Whitman and Whitman-Walker cases “resurrected” most of the 2016 Rule, but those courts expressly disclaimed any intention of altering the two portions of the rule Franciscan Alliance’s APA claim takes issue with.[30] It is also true that these injunctions and the agency’s threat to enforce Section 1557 harm Franciscan Alliance the same way the 2016 Rule’s termination of pregnancy and gender-identity clauses did (a topic discussed in more detail below). But those facts don’t make a difference. Franciscan Alliance cannot use the APA to vacate those injunctions or Section 1557. For Franciscan Alliance’s APA claim, then, the court is unable to provide relief beyond what the 2020 Rule already gave. The claim is therefore moot. When a claim becomes moot on appeal, we usually not only dismiss the action, but vacate the district court’s judgment as well.[31] But not always. Vacatur is an equitable remedy based on the idea that a “party who seeks review of the merits of an adverse ruling, but is frustrated by the vagaries of circumstance, ought not in fairness be forced to acquiesce in the judgment.”[32] The burden of proving entitlement to vacatur rests with the party seeking relief from the district court’s order.[33] The moving party must show that it was not responsible for the case becoming moot and that “the public interest would be served by a vacatur.”[34] Appellants cannot meet either prong. HHS caused Franciscan Alliance’s APA claim to become moot by passing the 2020 Rule. Nor would it be in the public interest to vacate the district court’s order. Usually when a new rule repeals an old rule, the chances are vanishingly small that the old rule will ever have legal effect again. But two district courts already used nationwide injunctions to reanimate much of the 2016 Rule. If we vacated the district court’s partial vacatur, the Whitman and Whitman-Walker courts, or some other court, could just as easily breathe new life into the remaining fragments of the 2016 Rule as well. Permitting important agency rules to flicker in and out of existence is detrimental to the rule of law. Appellants are not entitled to the equitable remedy of vacatur. Whether Franciscan Alliance’s RFRA claim is moot is an analytically distinct issue. HHS argues that Franciscan Alliance’s RFRA claims have also become moot because the 2016 Rule was replaced by the 2020 Rule. It is true that a case can become moot if the defendant ceases the allegedly unlawful conduct—including when a challenged statute, executive order, local ordinance, or regulation expires or is repealed. But “a defendant cannot automatically moot a case simply by ending its [allegedly] unlawful conduct once sued.”[35] “If that is all it took to moot a case, ‘a defendant could engage in unlawful conduct, stop when sued to have the case declared moot, then pick up where he left off, repeating this cycle until he achieves all his unlawful ends.’”[36] As a result, the burden rests with the defendant to demonstrate “that it is absolutely clear the allegedly wrongful behavior could not reasonably be expected to recur.”[37] HHS has not carried its burden. As the district court persuasively reasoned, the district court injunctions, the 2020 Rule, and the 2021 Interpretation combined to threaten Franciscan Alliance in the same way that the challenged portions of the 2016 Rule did. Since that time, it has become even clearer that Franciscan Alliance’s RFRA claim is not moot. Just months ago HHS issued the 2022 Notice, which warned covered entities like Franciscan Alliance that refusing to offer gender-reassignment surgeries violates Section 1557.[38] HHS has also repeatedly refused to disavow enforcement against Franciscan Alliance. In its brief on appeal, HHS simply says it “has not to date evaluated” whether it will enforce Section 1557 against Franciscan Alliance—in other words, it concedes that it may.[39] We have repeatedly held that plaintiffs have standing in the face of similar prosecutorial indecision.[40] In Pool v. City of Houston when the “City . . . indicated that it had not yet determined its position on the Charter requirements’ enforceability,” we held that the plaintiffs had standing to bring an “immediate[]” challenge.[41] In Speech First, Inc. v. Fenves the defendant vaguely promised to not enforce the challenged policies “contrary to the First Amendment”[42]—similar to HHS’s promise to “comply with the Religious Freedom Restoration Act . . . and all other legal requirements.”[43] We held that the plaintiffs had standing to bring suit because they were within the “class whose [conduct] is arguably restricted,” and the defendant’s promise was so vague that the scope of liability was both “unknown by the [defendant] and unknowable to those regulated by it.”[44] The cases cited by Appellants are inapposite. In Zimmerman v. City of Austin the plaintiff lacked standing because he failed to show “a serious intention to engage in conduct proscribed by law.”[45] Here, Franciscan Alliance already refuses to offer gender-reassignment surgeries or abortions. In Iowa Right to Life Committee, Inc. v. Tooker there was no credible threat of enforcement.[46] The Eighth Circuit certified the case to the Iowa Supreme Court, and its opinion was “clear” that the plaintiffs were not covered by the statute.[47] In this case there is substantial reason to believe that Franciscan Alliance falls within the scope of Section 1557, especially post-Bostock. The ACLU cites Wyoming v. U.S. Department of Interior.[48] In that case the district court’s challenged order “[b]y its terms . . . ha[d] expired” when a new rule had been enacted.[49] That challenge was moot because there was no longer any order to challenge, and any decision on whether the order was legally correct would have been purely advisory. The district court’s order in this case had no such expiration date. Finally, the ACLU cites State of Alaska v. Environmental Protection Agency.[50] In that case, the Ninth Circuit summarily dismissed the lawsuit because enforcement of the statute had been “indefinitely suspended.”[51] HHS has steadfastly refused to promise that it would not enforce Section 1557 or the 2016 Rule. In short, Franciscan Alliance’s APA claim is moot, its RFRA claim is not, and we leave the district court’s vacatur of the 2016 Rule in effect. B Appellants also take issue with the district court’s decision on remand to award a permanent injunction rather than just vacate the 2016 Rule. They argue that the district court erred in granting relief beyond the scope of Franciscan Alliance’s complaint because the complaint only sought relief from the 2016 Rule—not from Section 1557 more broadly. HHS’s point is more pragmatic than doctrinal. It notes that in a similar case the plaintiffs filed an amended complaint to seek relief against Section 1557 and explicitly requested an injunction like the one granted by the district court in this case.[52] HHS implies that if those plaintiffs were specific in their complaint, Franciscan Alliance could (and should) have been too. HHS’s argument relies on a false dichotomy. HHS implicitly argues that a lawsuit challenging a regulation and a lawsuit challenging the underlying statute are different. But as the Court recently noted in FEC v. Cruz, a challenge to an agency regulation is necessarily a challenge to the underlying statute as well. That’s because an agency “‘literally has no power to act’—including under its regulations—unless and until Congress authorizes it to do so by statute.”[53] In that case the government argued—as it does here—that plaintiffs who sued challenging the agency’s regulation had no standing to seek injunctive relief against enforcement of the statute. That argument rested on the faulty premise that the plaintiffs were “suing” a regulation. Rather, the Court said the right way to view the plaintiffs’ suit was as challenging “one Government action that causes their harm: the [Government's] threatened enforcement of the [statute], through its implementing regulation.”[54] HHS’s best case to the contrary is NYSRPA v. City of New York, where the Supreme Court declined to consider a damages claim that wasn’t requested in the complaint.[55] The Court noted that “the possibility of a damages claim was not raised until well into the litigation in this Court.”[56] But here, Franciscan Alliance sought a permanent injunction in its complaint. The essential form of relief sought has not changed—Franciscan Alliance seeks relief from HHS’s threat to prosecute hospitals that refuse to perform gender-reassignment surgeries and abortions. That stands in contrast to NYSRPA where the plaintiffs tried to fundamentally change the species of relief sought on appeal. And even if Appellants are right that Franciscan Alliance’s complaint did not seek relief against Section 1557 enforcement, Rule 54(c) allows district courts to grant “relief to which each party is entitled, even if the party has not demanded that relief in its pleadings.”[57] Appellants concede this point, but the ACLU responds that courts cannot give unrequested relief if it would “prejudice” the opponent. And it argues that it is prejudiced because HHS might have offered different narrow tailoring arguments if it realized it was defending Section 1557 itself, not just the 2016 Rule. But the ACLU seems to have not read the case it cites, Portillo v. Cunningham, closely enough. Portillo says that when a party has a chance to argue whether the proposed relief is improper, “there is no prejudice.”[58] A party is only prejudiced if the proposed relief is not “tested adversarially, tried by consent, or at least developed with meaningful notice to the defendant.”[59] Franciscan Alliance’s proposed relief was briefed extensively by both sides—both on remand and on appeal. No surprise means no prejudice. More importantly, to show prejudice Appellants cannot vaguely assert that they might have made different narrow tailoring arguments. Appellants gave the district court no clues as to what, exactly, the prejudice was. These arguments have not been refined on appeal. To the contrary, the ACLU concedes in its brief that the substantial-burden analysis is identical whether Franciscan Alliance is challenging Section 1557 or the 2016 Rule. The ACLU’s concession is well taken. As discussed above, Cruz said that there is no metaphysical difference between a challenge to a rule and the underlying statute because “[a]n agency’s regulation cannot ‘operate independently of’ the statute that authorized it.”[60] Nothing in the district court’s strict- scrutiny analysis, or its analysis on the permanent injunction factors, depended on whether the 2016 Rule or the underlying statute were being challenged.[61] Finally, Appellants argue that Franciscan Alliance lacks standing to seek a permanent injunction against future regulations that may require it to perform abortions or gender-reassignment surgeries. Appellants argue that they may make different arguments about narrow tailoring in the future, and that the district court violated Article III when it granted Franciscan Alliance a permanent injunction against hypothetical future Section 1557 enforcement. As noted above, Appellants give no clues about what these different arguments would be. Besides, this argument proves too much. It is always true that the Government’s interest may subtly evolve over time. If that hypothetical chance is enough to defeat standing, then plaintiffs could never obtain injunctive relief to prevent future violations of the Free Speech Clause, the Equal Protection Clause, or any other lawsuit where means/ends scrutiny is involved. But that can’t be right. Courts have issued permanent injunctions in these contexts countless times.[62] Throughout its storied history the ACLU has sought and obtained multiple permanent injunctions against statutes that failed heightened scrutiny.[63] In contrast, Appellants do not cite a single case where a court refused to grant a permanent injunction because of the hypothetical chance that the Government could advance a compelling government interest sometime in the future. We see no reason to be the first court to do so. C Finally, the ACLU—but not HHS— argues that the district court erred in granting the permanent injunction because Franciscan Alliance did not satisfy the irreparable harm standard. To obtain a permanent injunction, Franciscan Alliance had to show that “the failure to grant the injunction [would] result in irreparable injury.”[64] We have recognized that the loss of freedoms guaranteed by the First Amendment, RLUIPA, and RFRA all constitute per se irreparable harm.[65] Again, the ACLU gives us no reason to rethink those precedents. And even if it did, the rule of orderliness prevents us from doing so. III Franciscan Alliance’s APA claim is DISMISSED as moot. In all other respects, the judgment of the district court is AFFIRMED.
