Reversed and vacated by published opinion. Judge GREGORY wrote the majority opinion, in which Judge KING joined. Judge SHEDD wrote a dissenting opinion.
OPINION
GREGORY, Circuit Judge:In these consolidated appeals, William T. Hatcher, Richard Dean Hinen, Gregory V. Roberts, and John Edward Sawn appeal their convictions. Each of the Appellants was convicted of knowingly failing to register or update their registration as required by the Sex Offender Registration and Notification Act (“SORNA”), in violation of 18 U.S.C. § 2250(a) (2006). The Appellants argue that SORNA is unconstitutional because it is not a valid exercise of congressional authority and because it violates the non-delegation doctrine, the Ex Post Facto Clause, and the Due Process Clause of the Fifth Amendment. However; we need not reach these constitutional questions because we find that, as a matter of statutory interpretation, SORNA’s registration requirements did not apply to the Appellants *224at the time they committed the acts giving rise to their indictments. Therefore, we must reverse the convictions and vacate the sentences imposed in connection with those convictions.
I.
The Appellants were convicted of sex offenses in state courts between 1993 and 2001. All of the Appellants had finished serving the sentences imposed on them for those offenses prior to July 27, 2006, the enactment date of SORNA. As a result of their convictions, the Appellants were required to register under the sex offender registration systems of their respective states, and all of the Appellants initially complied with those registration requirements. At various times between July 27, 2006, and February 28, 2007, the Appellants moved to other states and failed to comply with SORNA’s continuing registration requirements.
The Appellants were indicted on one count of traveling in interstate or foreign commerce and knowingly failing to register or update a sex offender registration as required by SORNA, in violation of 18 U.S.C. § 2250(a) (2006). Each of the Appellants was indicted after February 28, 2007.1 The Appellants filed motions to dismiss their respective indictments, but those motions were denied by the district courts.2 Hatcher, Roberts, and Sawn each entered a conditional guilty plea, preserving the right to appeal the denial of the motion to dismiss. Hinen was convicted in a jury trial.
Hatcher was sentenced to three years probation and ordered to pay a mandatory special assessment. Hinen was sentenced to three years probation, fined $450, and ordered to pay a mandatory special assessment. Roberts was sentenced to time served, five years supervised release, and ordered to pay a mandatory special assessment. Sawn was sentenced to thirty months imprisonment, five years supervised release, and ordered to pay a mandatory special assessment. The Appellants timely appeal.
II.
This Court reviews de novo the district court’s denial of a motion to dismiss an indictment where the denial depends solely on questions of law. United States v. United Med. & Surgical Supply Corp., 989 F.2d 1390, 1398 (4th Cir.1993); see also United States v. Brandon, 298 F.3d 307, 310 (4th Cir.2002).
III.
A.
On July 27, 2006, the Adam Walsh Child Protection and Safety Act of 2006 (“AWA”) was signed into law. Pub.L. No. 109-248, §§ 101-55, 120 Stat. 587, 590-611 (2006). Title I of the AWA is SORNA, which was enacted for the purpose of “protecting] the public from sex offenders and offenders against children” through the creation of a “comprehensive national system for the registration of those offenders.” 42 U.S.C.A. § 16901 (West 2008). To that end, jurisdictions must “maintain a juris*225diction-wide sex offender registry” that complies with the standards set out by SORNA. 42 U.S.C.A. § 16912(a) (West 2008). Sex offenders are required to provide several types of information for inclusion in the sex offender registry, including their names and aliases, Social Security numbers, addresses of residences, names and addresses of places of employment, names and addresses of educational institutions in which the offenders are enrolled, and vehicle information. 42 U.S.C.A. § 16914(a) (West 2008).
In addition to detailing the kinds of information that must be included in the sex offender registry, SORNA dictates when and how convicted sex offenders must register. See 42 U.S.C.A. § 16913 (West 2008). As a general matter, sex offenders must register and keep their registration current in each jurisdiction where they reside, work, or attend school. 42 U.S.C.A. § 16913(a) (West 2008). Sex offenders are required to initially register in one of two ways: if the sex offender was sentenced to a term of imprisonment for his underlying offense, he must register before completing the sentence of imprisonment for that offense; otherwise, the sex offender must register within three days of being sentenced for the offense. 42 U.S.C.A. § 16913(b) (West 2008). Following the initial registration, sex offenders must keep their registration current by notifying at least one jurisdiction where they are required to register of all changes of name, residence, employment, or student status within three days of the change. 42 U.S.C.A. § 16913(c) (West 2008).
Of particular importance to this appeal is 42 U.S.C.A. § 16913(d) (West 2008), titled, “Initial registration of sex offenders unable to comply with subsection (b) of this section.” This subsection is located within the same section as the aforementioned registration requirements. According to § 16913(d),
The Attorney General shall have the authority to specify the applicability of the requirements of this subchapter to sex offenders convicted before July 27, 2006 [SORNA’s enactment date] or its implementation in a particular jurisdiction, and to prescribe rules for the registration of any such sex offenders and for other categories of sex offenders who are unable to comply with subsection (b) of this section.
To enforce its registration provisions, SORNA includes 18 U.S.C. § 2250(a) (2006), which makes it a federal felony, punishable by up to ten years imprisonment, inter alia, for a person who is required to register under SORNA to travel in interstate commerce and knowingly fail to register or update his sex offender registration.
On February 28, 2007, after the Appellants had committed the acts giving rise to their indictments, the Attorney General issued an interim rule stating that the registration requirements of SORNA applied to all convicted sex offenders, including those offenders who were convicted of sex offenses prior to the enactment of SORNA (“pre-SORNA offenders”). 72 Fed.Reg. 8894, 8896 (Feb. 28, 2007). According to the Attorney General, the purpose of the interim rule was to “foreclosfe] any dispute as to whether SORNA is applicable where the conviction for the predicate sex offense occurred prior to the enactment of SORNA.” Id. The Attorney General cited § 16913(d) as the source of his authority to promulgate the rule, “regardless of whether SORNA would apply with such scope absent this rule.” Id.
B.
The Appellants argue that the district courts erred in denying their motions to *226dismiss because the registration requirements of SORNA did not apply to them at the time they committed their alleged SORNA violations. The Appellants were convicted of their underlying sex offenses and had completed their sentences prior to the enactment of SORNA. Their indictments for violations of SORNA related to conduct that was committed sometime between SORNA’s enactment and the issuance of the interim rule regarding the applicability of SORNA to pre-SORNA offenders. According to the Appellants, until the Attorney General issued the interim rule, SORNA’s application to pre-SORNA offenders was not established, and thus the Appellants should not have been charged with violating SORNA’s registration requirements.
In order to rule on the merits of the Appellants’ claim, we must interpret the meaning of 42 U.S.C.A. § 16913(d) (West 2008). Other circuits have recently weighed in on this issue, albeit with differing results. Compare United States v. Madera, 528 F.3d 852 (11th Cir.2008) (per curiam) (holding that SORNA’s registration requirements did not apply to pre-SORNA offenders until the issuance of the interim rule), with United States v. May, 535 F.3d 912 (8th Cir.2008) (holding that SORNA’s registration requirements applied to pre-SORNA offenders from the time of SORNA’s enactment) and United States v. Hinckley, 550 F.3d 926 (10th Cir.2008) (same).
To ascertain the meaning of § 16913(d), this Court must first examine the plain language of the subsection. See Hillman v. IRS, 250 F.3d 228, 232 (4th Cir.2001). As a general rule, “when the terms of a statute are clear, its language is conclusive and courts are ‘not free to replace ... [that clear language] with an unenacted legislative intent.’ ” United States v. Morison, 844 F.2d 1057, 1064 (4th Cir.1988) (quoting INS v. Cardoza-Fonseca, 480 U.S. 421, 453, 107 S.Ct. 1207, 94 L.Ed.2d 434 (1987) (Scalia, J., concurring)). This Court recognizes two “exceptionally rare” exceptions to this rule: (1) “when literal application of the statutory language at issue produces an outcome that is demonstrably at odds with clearly expressed congressional intent to the contrary,” and (2) “when literal application of the statutory language at issue ‘results in an outcome that can truly be characterized as absurd.’ ” Hillman, 250 F.3d at 233 (quoting Sigmon Coal Co. v. Apfel, 226 F.3d 291, 304 (4th Cir.2000)).
Only if we determine that the terms of a statutory provision are ambiguous are we then permitted to consider other evidence to interpret the meaning of the provision, including the legislative history and the provision’s heading or title. See Ratzlaf v. United States, 510 U.S. 135, 147-48, 114 S.Ct. 655, 126 L.Ed.2d 615 (1994) (“[W]e do not resort to legislative history to cloud a statutory text that is clear.”); Bhd. of R.R. Trainmen v. Balt. & Ohio R.R. Co., 331 U.S. 519, 528-29, 67 S.Ct. 1387, 91 L.Ed. 1646 (1947) (“[T]he title of a statute and the heading of a section cannot limit the plain meaning of the text. For interpretative purposes, they are of use only when they shed light on some ambiguous word or phrase.” (internal citations omitted)).
Applying these principles of statutory interpretation, we find that SORNA’s registration requirements did not apply to pre-SORNA offenders until the Attorney General issued the interim rule specifying the applicability of SORNA’s registration requirements to those offenders. Examining the plain language of § 16913(d), the subsection contains two clauses. The first clause states that the Attorney General “shall have the authority to specify the applicability of the requirements of this *227subchapter to sex offenders convicted before July 27, 2006 or its implementation in a particular jurisdiction.” 42 U.S.C.A. § 16913(d) (West 2008). This clause, fairly read, delegates to the Attorney General the authority to specify the requirements of SORNA3 for all sex offenders who were convicted before the enactment of SOR-NA.4 Madera, 528 F.3d at 858. Congress’ use of the phrase “shall have the authority” indicates that Congress is giving the Attorney General exclusive authority to determine the applicability of SOR-NA to pre-SORNA offenders, and that, until such a determination is made, SOR-NA’s requirements would apply only prospectively and not to pre-SORNA offenders such as the Appellants. See id. at 857; Hinckley, 550 F.3d 926, at 949 (McConnell, J., dissenting). The Appellants’ indictments were based on conduct occurring prior to the Attorney General’s issuance of the interim rule, at a time when SORNA’s registration requirements did not yet apply to them. Therefore, they cannot be prosecuted for conduct that was not criminal at the time it was committed. See Landgraf v. USI Film Prods., 511 U.S. 244, 265, 114 S.Ct. 1483, 128 L.Ed.2d 229 (1994) (“[T]he legal effect of conduct should ordinarily be assessed under the law that existed when the conduct took place .... ” (internal quotation omitted)).
In the second clause of § 16913(d), Congress delegates to the Attorney General the authority to prescribe the registration rules “of any such sex offenders and for other categories of sex offenders who are unable to comply with subsection (b) of this section.” The second clause of the subsection thus gives the Attorney General the authority to promulgate registration rules for two distinct groups of sex offenders: (1) sex offenders who were convicted before July 27, 2006, and (2) offenders who are unable to comply with subsection (b), the subsection containing SORNA’s initial registration requirements. Madera, 528 F.3d at 858; Hinckley, 550 F.3d 926, at 949-50 (McConnell, J., dissenting). Reading the first clause in conjunction with the second clause, it follows that the Attorney General has the authority both to “specify the applicability” of SORNA with regard to pre-SORNA offenders and to prescribe registration rules for all pre-SORNA offenders and for other sex offenders who are unable to comply with the initial registration requirements.
The Government contends, however, that § 16913(d) is ambiguous, which would warrant looking beyond the plain language of the subsection to its title, “Initial registration of sex offenders unable to comply with subsection (b) of this section.” According to the Government, this title serves to narrow the scope of the Attorney General’s authority to specify the applicability of SORNA’s registration requirements, so that it extends only to those pre-SORNA offenders who are unable to comply with the initial registration require*228ments. Since the Appellants were able to initially register under the sex offender registration systems of their respective states, they do not fall within this narrow category of offenders, and thus SORNA’s registration requirements applied to them from the time of SORNA’s enactment.
Indeed, those circuits that have held that SORNA’s registration requirements applied to pre-SORNA offenders at the time of SORNA’s enactment have done so based on a finding that the language of § 16913 is ambiguous. See May, 535 F.3d at 918; Hinckley, 550 F.3d 926, 931-32. Specifically, those circuits have adopted the reasoning of United States v. Beasley, No. 1:07-CR-115-TCB, 2007 U.S. Dist. LEXIS 85793 (N.D.Ga. Oct.10, 2007), which found an ambiguity in the second clause of subsection (d). May, 535 F.3d at 918-19; Hinckley, 550 F.3d 926, 931-32. According to Beasley,
An additional possible meaning of subsection (d) is that past offenders (“offenders convicted before the enactment of this Act”) are included within (and not a separate group from) the broader category of “sex offenders who are unable to comply with subsection (b),” and it is only as to those “sex offenders who are unable to comply with subsection (b)” that the Attorney General was given authority under subsection (d) to issue clarifying regulations.
2007 U.S. Dist. LEXIS 85793, at *17-18, 2007 WL 3489999, at *6; accord May, 535 F.3d at 918; Hinckley, 550 F.3d 926, 931-32.
However, this alternative interpretation of § 16913(d) is foreclosed by the plain language of the subsection. The second clause of the subsection specifies that the Attorney General may prescribe registration rules for “such sex offenders,” i.e. pre-SORNA offenders, and for “other categories of sex offenders” who are unable to comply with the initial registration requirements. 42 U.S.C.A. § 16913(d) (West 2008); see also Hinckley, 550 F.3d 926, 951 (McConnell, J., dissenting). It is thus clear that the category of pre-SORNA offenders is a distinct category from “categories of sex offenders who are unable to comply with subsection (b),” and the category of pre-SORNA offenders is not included within this latter group. To interpret § 16913(d) as including the set of pre-SORNA offenders within the set of “categories of sex offenders who are unable to comply within subsection (b)” ignores the term “other,” which indicates that the two sets are distinct. “It would be like interpreting a statute that applies to ‘humans and to other categories of primate who walk on two legs’ as excluding paraplegic humans.” Hinckley, 550 F.3d 926, 951 (McConnell, J., dissenting).
Moreover, such an interpretation of § 16913(d) overlooks the first clause of the subsection, which states that the Attorney General has the authority to determine SORNA’s applicability to pre-SORNA offenders, and that clause has no language limiting its scope to cover only those pre-SORNA offenders who are also unable to comply with the initial registration requirements of subsection (b). If this Court were to find that such a narrow reading of the subsection were plausible, we would effectively have to read limiting language into the first clause. Had Congress intended to delegate to the Attorney General only the authority to determine SORNA’s applicability for past offenders who were also unable to comply with subsection (b), it would have been quite easy for Congress to do so by including limiting language in the first clause of the subsection. However, Congress did not do so, and this Court should not “ ‘replace ... [that clear language] with an unenacted legislative intent.’ ” Morison, 844 F.2d at *2291064 (quoting INS v. Cardoza-Fonseca, 480 U.S. 421, 453, 107 S.Ct. 1207, 94 L.Ed.2d 434 (1987) (Scalia, J., concurring)).
Nor can we say that applying the plain language of the subsection runs counter to clearly expressed congressional intent or produces an absurd outcome. See Hillman, 250 F.3d at 233. Although Congress’ intent in passing SORNA was to create a comprehensive national system for the registration of sex offenders, 42 U.S.C.A. § 16901 (West 2008), our interpretation of the subsection does not eviscerate such a comprehensive registration system and in fact arguably helps to achieve such a system. The subsection delegated to the Attorney General the authority to determine whether SORNA’s requirements apply to pre-SORNA offenders, and on February 28, 2007, the Attorney General issued an interim rule exercising that authority. Now that the Attorney General has issued the interim rule, there can be no doubt that SORNA’s registration requirements now apply to pre-SORNA offenders. Given the patchwork of state approaches towards sex offender registration that existed prior to the enactment of SORNA, it was not “absurd” for Congress to delegate this authority to the Attorney General, with the intent that he exercise it to effectuate a comprehensive registration system.
It is important to note that the decision reached today is quite narrow, for we do not hold that SORNA’s registration requirements do not apply to persons who were convicted of sex offenses prior to SORNA’s enactment date. Rather, we hold only that SORNA’s registration requirements did not apply to pre-SORNA offenders until the Attorney General issued the interim rule on February 28, 2007.
IV.
Because the Appellants’ indictments were based on conduct that pre-dated the Attorney General’s interim rule specifying that SORNA’s registration requirements applied to pre-SORNA offenders, we reverse the Appellants’ convictions and vacate the sentences imposed in connection with those convictions.
REVERSED AND VACATED
. Hatcher was initially charged via criminal complaint on February 23, 2007, with violating 18 U.S.C. § 2250(a) (2006), but he was later indicted for the same charge on March 6, 2007.
. Hinen and Roberts argued in their motions to dismiss that the Western District of Virginia was an improper venue for the action, but the district courts found venue to be proper. Because we hold that the district courts erred in denying the Appellants’ motions to dismiss on other grounds, we need not consider this alternative ground for reversal.
. The term "this subchapter” refers to Sub-chapter I, "Sex Offender Registration and Notification,” which contains all of SORNA’s registration requirements.
. The dissent contends that if § 16913(d) is read in the context of SORNA’s other provisions, "subsection (d) merely authorizes the Attorney General to exempt persons with sex offenses that predate July 27, 2006, from SORNA’s reach.” (Dis.Op. 233). Furthermore, in reaching this interpretation of § 16913(d), the dissent concludes that the subsection is unambiguous.
Curiously, the dissent’s finding that § 16913(d) is "unambiguous” requires it to substitute the term "applicability” that actually appears in § 16913(d) with the term "exemption,” which does not appear. Thus, while the dissent claims merely to adhere to the plain language of the subsection, its interpretation in fact revises one of its pivotal terms.