ORDER AND AMENDED OPINION
ORDER
DefendanU-Appellant’s petition for panel rehearing, filed June 5, 2006, is GRANTED. The disposition filed on April 21, 2006 is amended and replaced by the disposition filed concurrently with this order. No further petitions for rehearing will be entertained by this court.
OPINION
Defendant-appellant Gumercindo Salazar-Gonzalez (“Salazar-Gonzalez”) appeals his conviction for being found in the United States without the consent of the Attorney General in violation of 8 U.S.C. § 1326. We have jurisdiction under 28 U.S.C. § 1291. At trial, the district court refused to give Salazar-Gonzalez’s proposed jury instruction requiring the government to prove beyond a reasonable doubt that Salazar-Gonzalez “voluntarily reentered” and “knew he was in” the United States. The district court concluded that Salazar-Gonzalez presented no evidence to support a voluntariness instruction, but did not separately address the knowledge instruction. Although this was in error, we affirm the district court nonetheless because it is “clear beyond a reasonable doubt that a rational jury would have found the defendant guilty absent the error[.]” Neder v. United States, 527 U.S. 1, 18, 119 S.Ct. 1827, 144 L.Ed.2d 35 (1999). However, because Salazar-Gonzalez preserved his nonconstitutional Booker claim that he is entitled to resentencing under the now-advisory Sentencing Guidelines, and the district court’s error in sentencing him under the mandatory regime was not harmless, we vacate and remand for resentencing under the advisory regime. United States v. Beng-Salazar, 452 F.3d 1088 (9th Cir.2006).
I.
On October 23, 2003, Border Patrol Agent Raul Castoreña noticed footprints crossing the unmarked United States-Mexico border fence near Jacumbá, California. After following these footprints for approximately 100 yards, Castoreña found Salazar-Gonzalez, sitting with 10 other people, partially obscured in moderately dense brush. He ordered them not to move and then asked their citizenship and if they “had proper documents to be legally present in the United States.” All of the individuals, including Salazar-Gonzalez, responded that they were citizens of Mexico and did not have documents authorizing them to be in the United States.
Salazar-Gonzalez, who had been convicted of crimes in the United States and deported on three previous occasions, most recently on October 20, 2003, was charged and convicted with being found in the United States after deportation in violation of 8 U.S.C. § 1326. The district court increased Salazar-Gonzalez’s base offense level by 16 levels pursuant to U.S.S.G. § 2L1.2, based on his being deported after sustaining a conviction for a crime of violence, and it increased his criminal history category from level IV to V, based on its finding that two prior convictions arose from separate arrests. The district court sentenced Salazar-Gonzalez to 70 months’ imprisonment, a sentence in the middle of the range prescribed by the United States Sentencing Guidelines.
II.
Preliminarily, we address the district court’s denial of Salazar-Gonzalez’s motion to exclude a “Certificate of Nonexistence of Record” (“CNR”) submitted by the government to prove that Salazar-*854Gonzalez had not received the Attorney General’s permission to apply for readmission to the United States. See 8 U.S.C. § 1326 (“[A]ny alien who — (1) has been ... deported ... and thereafter (2) ... is at any time found in, the United States, unless (A) ... the Attorney General has expressly consented to such alien’s reapplying for admission ..., shall be fined under Title 18, or imprisoned not more than 2 years, or both.” (emphasis added)). Salazar-Gonzalez contends that admission of the CNR violated his Sixth Amendment right to confront witnesses against him, as articulated by the Supreme Court in Crawford v. Washington, 541 U.S. 36, 124 S.Ct. 1354, 158 L.Ed.2d 177 (2004). The CNR is not testimonial evidence under Crawford; the district court properly admitted it as a nontestimonial public record. United States v. Cervantes-Flores, 421 F.3d 825, 834 (9th Cir.2005).
III.
Salazar-Gonzalez principally challenges the district court’s refusal to give a jury instruction on the general intent element of being a deported alien “found in” the United States under § 1326.1 At trial, Salazar-Gonzalez offered as his defense that he had not knowingly and voluntarily entered the United States but rather wandered into the country inadvertently, without knowing that he was crossing the border. Salazar-Gonzalez proposed a jury instruction specifying that the jury must, in order to convict, find that he had “voluntarily reentered the United States” and “knew he was in the United States.” His proposed instruction concluded: “It is not sufficient that the government proves that Mr. Salazar was ‘found in’ the United States; rather, it must prove that Mr. Salazar committed an intentional act, that is, a voluntary entry.”
Although the district court agreed that a “voluntariness” instruction “could be applicable” and “certainly not frivolous” in some cases, the court rejected Salazar-Gonzalez’ proposed instruction, concluding that “in this case the evidence does not warrant it.” The court instead instructed the jury as follows:
In order for the defendant to be found guilty of [being a deported alien found in the United States], the government must prove each of the following elements beyond a reasonable doubt: First, the defendant is an alien; second, the defendant was deported or removed from the United States; ... third, the defendant was subsequently found in the United States; and fourth, at the time the defendant was found in the United States he did not have the consent of the United States Attorney General or his designated successor, the Secretary of the Department of Homeland Security, (emphasis added).
“We review de novo the district court’s interpretation of the requisite elements of a federal offense.” United States v. Jime*855nez-Borja, 378 F.3d 853, 857 (9th Cir.2004). The omission of an element from jury instructions is subject to harmless-error analysis. Neder, 527 U.S. at 10, 119 S.Ct. 1827.
A.
This case highlights an area of confusion in our § 1326 jurisprudence that we now clarify. As an initial matter, the district court erroneously construed Salazar-Gonzalez’s proposed jury instruction — which required the jury to find that he both “voluntarily reentered” and “knew he was in” the United States — -as a “voluntariness” instruction only. Although § 1326 does not include an express mens rea element, our cases make clear that being “found in” the United States under § 1326 is a crime of “general intent.” See, e.g., United States v. Rivera-Sillas, 417 F.3d 1014, 1020 (9th Cir.2005) (“A ‘found in’ offense under § 1326 is a general intent crime.”); United States v. Pina-Jaime, 332 F.3d 609, 613 (9th Cir.2003) (“[B'Jeing found in the United States in violation of § 1326(a)(2) is a crime of general intent. ...”). We have also held that “voluntariness of the return is an element of the [“found in” offense] and, as such, must be proved beyond a reasonable doubt by the prosecution.” United States v. Quintana-Torres, 235 F.3d 1197, 1200 (9th Cir.2000); see also United States v. Salazar-Robles, 207 F.3d 648, 650 (9th Cir.2000) (upholding a “found in” conviction and finding that “[t]he voluntary element consisted in Salazar Robles’s return”).
However, a general intent mens rea also requires that a “defendant possessed knowledge with respect to the actus reus of the crime.” Carter v. United States, 530 U.S. 255, 268, 120 S.Ct. 2159, 147 L.Ed.2d 203 (2000); see also United States v. Gracidas-Ulibarry, 231 F.3d 1188, 1196 (9th Cir.2000) (en banc) (“In general, ‘purpose’ corresponds to the concept of specific intent, while ‘knowledge’ corresponds to general intent.”). To act with general intent, a defendant must know the facts that make his actions illegal, but not that the action itself is illegal. That is, the defendant need only intend to perform the underlying prohibited action, not to break the law. Thus, the Supreme Court has held that a federal firearms statute, construed as requiring a mens rea of general intent, requires the government to prove that a defendant knew he possessed a firearm with the features barred by the statute, even if he was unaware that the law forbade possession of such a firearm. Staples v. United States, 511 U.S. 600, 619, 114 S.Ct. 1793, 128 L.Ed.2d 608 (1994). Similarly, a defendant may be found guilty of a crime requiring general intent to steal if he knowingly and voluntarily “t[ook the] property of another by force and violence or intimidation” even if he intended to return the property later. Carter, 530 U.S. at 268, 120 S.Ct. 2159; see also Gracidas-Ulibarry, 231 F.3d at 1194 (explaining that if attempted illegal reentry were a general intent crime, a previously deported alien who went to the border to pick hp forms to apply for reentry could be convicted of attempting to reenter, regardless of his or her intent to comply with the law).
For example, in Riverctr-Sillas, the defendant challenged an indictment charging him with being found in the United States in violation of § 1326 on the ground that it failed to charge him with “knowing that he was in the United States.” 417 F.3d at 1020. We first held that the general intent mens rea of the § 1326 “found in” offense required that a defendant act voluntarily and knowingly, id. (citing United States v. Berrios-Centeno, 250 F.3d 294, 299 (5th Cir.2001)); we then concluded that knowledge, like voluntariness, can be inferred from the fact of the defendant’s presence in the United States and need not be expressly pled in an indictment, id. The *856government’s argument that Rivera-Sillas’ discussion of knowing entry must be either dictum or incorrect lacks merit.2 It is true that we have addressed the voluntariness element of the § 1326 crime on many occasions and that Rivera-Sillas is the first case to address plainly the question of knowledge.3
Supreme Court law and our decisions make clear, however, that Rivera-Sillas correctly concluded that a defendant must enter or remain in the United States knowingly as well as voluntarily to be convicted under the general intent crime of being “found in” the United States under § 1326. See also Pena-Cabanillas v. United States, 394 F.2d 785, 790 (9th Cir.1968) (explaining that § 1326 requires that “[t]here ... be the general intent to do the prohibited act, to-wit enter,” and upholding the defendant’s conviction under § 1326 for “knowingly and wilfully entering] the United States”).
We therefore hold that for a defendant to be convicted of a § 1326 “found in” offense, the government must prove beyond a reasonable doubt that he entered voluntarily and had knowledge that he was committing the underlying act that made his conduct illegal — entering or remaining in the United States.4
B.
The Supreme Court has long held that the Due Process Clause requires the government to prove each element of the crime beyond a reasonable doubt. In re Winship, 397 U.S. 358, 90 S.Ct. 1068, 25 L.Ed.2d 368 (1970). This same bedrock constitutional principle also entails a concomitant right for the defendant to have a jury instruction on each element of the crime. See United States v. Gaudin, 515 U.S. 506, 511, 115 S.Ct. 2310, 132 L.Ed.2d 444 (1995); United States v. Perez, 116 F.3d 840, 847 (9th Cir.1997) (en banc) (“Failure to submit an essential element to a jury relieves the prosecution of its obligation to prove every element beyond a reasonable doubt.”). Because “knowledge” *857is a separate element of the “found in” offense that, like voluntariness, the government must prove beyond a reasonable doubt, we hold that the district court erred in refusing to instruct the jury on the elements of knowledge and voluntary entry.
We recognize that some of our cases interpreting § 1326, when taken out of context, might be read to suggest that the statute establishes a rebuttable presumption on the element of general intent, i.e., that the government need not prove in a “found in” case that a previously deported alien who is apprehended in the United States entered the country knowingly and voluntarily. See, e.g., Rivera-Sillas, 417 F.3d at 1020 (‘We are comfortable presuming that a defendant who is found in the United States willfully and knowingly acted in order to enter this country.”); Quintana-Torres, 235 F.3d at 1200 (“To dispel the inference [of general intent to be here], the alien would have to demonstrate that one of the speculative possibilities of involuntary entry had actually taken place.”). However, a close reading of our case law dispels that suggestion. First, even those cases that have discussed the defendant’s ability to rebut the inference of intent by submitting evidence of involuntary entry have consistently described § 1326 as allowing only permissible inferences regarding the defendant’s general intent to commit the crime. See, e.g., Rivera-Sillas, 417 F.3d at 1021 (“Because involuntary presence in the United States is the rare exception and not the rule, however, we allow an inference of voluntariness where the defendant has raised no evidence to the contrary.” (emphasis added)); Qwintana-Torres, 235 F.3d at 1200 (“[A] reasonable juror may well infer that the alien had the intention to be here when the alien is discovered at any location in the country other than the border.” (emphasis added)). But nothing in our § 1326 jurisprudence suggests that such permissible inferences relieve the government of its burden to prove the “general intent” element of the crime of being “found in” the United States.
To the contrary, our case law is consistent with the proposition that the government must prove that the alien’s presence in the country is both knowing and voluntary. See, e.g., Quintana-Torres, 235 F.3d at 1199 (rejecting the government’s argument in a “found in” case that it did not have to prove that the defendant “intentionally reentered” the United States). Indeed, in most of our cases involving the “general intent” requirement of the “found in” offense, the defendant has challenged either the sufficiency of an indictment to which he pled guilty or the sufficiency of the evidence to support his conviction after being apprehended well béyond the United States border. See Rivera-Sillas, 417 F.3d at 1017 (challenging the indictment and sufficiency of the evidence); United States v. San Juan-Cruz, 314 F.3d 384, 390 (9th Cir.2002) (challenging the indictment); Parga-Rosas, 238 F.3d at 1211 (challenging the indictment and sufficiency of the evidence); Quintana-Torres, 235 F.3d at 1199 (challenging sufficiency of the evidence). In these contexts, we have declined to reverse the convictions of aliens who were “found in” the United States because we have recognized that a jury might validly draw the factual inference that an alien who is apprehended well within the United States has usually committed a knowing and voluntary act to be here. We have, in other words, indulged the factual inference that an alien’s discovery at a location in the United States “other than the border” is “circumstantial proof’ that the alien had the general intent to enter. See Quintana-Torres, 235 F.3d at 1200; see also Riverar-Sillas, 417 F.3d at 1021 (holding that the “general intent of the defendant to reenter the United States may be inferred from the fact that the *858defendant was previously deported and was subsequently found in the United States”).
However, we have never strayed from requiring proof of “general intent” as an essential ingredient of a conviction under § 1326. Nor have we ever suggested that the defense must present evidence in order to obtain a jury instruction on that element of the crime (i.e., that the defendant voluntarily and knowingly acted to enter the United States). Indeed, constitutional principles preclude such suggestions. See, e.g., Gaudin, 515 U.S. at 511, 115 S.Ct. 2310 (explaining that “[t]he Constitution gives a criminal defendant the right to demand that a jury find him guilty of all the elements of the crime with which he is charged”). Instead, the government’s burden to prove “general intent” under § 1326 exists whether or not the defendant comes forward with evidence demonstrating that he lacked such intent. Because the district court refused to instruct the jury on the elements of knowledge and voluntariness, Salazar-Gonzalez’ right to have a jury instruction on each element of the crime was violated.
Despite this error, we nonetheless affirm the conviction because it is “clear beyond a reasonable doubt that a rational jury would have found the defendant guilty absent the error.” Neder, 527 U.S. at 18, 119 S.Ct. 1827 (holding that the omission of an element from jury instructions is subject to harmless error review). The uncontroverted evidence reveals that Salazar-Gonzales was found hiding in the brush with 10 other people, all of whom told the border patrol that they were citizens of Mexico and did not have authorization to be in the United States. Although the group was apprehended only 100 yards from the border, which was unmarked, the area is demarcated by a fence that ranges from 4 to 11 feet in height.5 In addition, Agent Castoreña testified that he saw footprints on the Mexican side of the border that approached the fence, crossed it and continued in a northerly direction into the United States. Agent Castoreña further testified that he followed these foot-prints “approximately 100 yards north of the border road” until he “came across brush,” where he noticed the 11 individuals “trying to conceal themselves.”
It is unreasonable to believe that 11 Mexican nationals could cross such a barrier from a far northern point in the Mexican countryside involuntarily or without knowing that they were entering the United States. Moreover, Salazar-Gonzales presented no evidence of involuntary or unknowing entry other than the description of this fence and the isolated surrounding area. Cf. Jimenez-Borja, 378 F.3d at 858 (holding that the district court’s failure to instruct the jury on the element of voluntary entry in a “found in” case was harmless because the defendant was “well within the borders of the United States,” and there was no evidence to suggest that he came to be there involuntarily). Under these circumstances, the record does not contain “evidence that could rationally lead to a contrary finding with *859respect to the omitted element” of knowing and voluntary entry. Neder, 527 U.S. at 19, 119 S.Ct. 1827. Accordingly, we AFFIRM Salazar-Gonzalez’ conviction.
C.
Salazar-Gonzalez also argues that the district court unconstitutionally enhanced his sentence under the then-mandatory Sentencing Guidelines based on facts not alleged in the indictment or proven to a jury, in violation of his Sixth Amendment rights and Apprendi v. New Jersey, 530 U.S. 466, 120 S.Ct. 2348, 147 L.Ed.2d 435 (2000). Specifically, the district court increased Salazar-Gonzalez’s criminal history score by three points, which resulted in a one level increase to his criminal history category, after finding that he had committed two previous, unrelated offenses under U.S.S.G. § 4A1.2(a)(2). However, Salazar-Gonzalez was sentenced on the same day for his two previous crimes, and his sentences were imposed concurrently. Although the fact of a prior conviction may be found by a district court using a preponderance of the evidence standard, see Almendarez-Torres v. United States, 523 U.S. 224, 118 S.Ct. 1219, 140 L.Ed.2d 350 (1998), Salazar-Gonzalez argues that the district court here did more than merely determine that he had a prior conviction. Rather, he contends that the district court had to examine a number of documents, including several police reports regarding arrests that had occurred between the two offenses for which Salazar-Gonzalez was convicted, to find that his prior convictions were unrelated offenses. Salazar-Gonzalez argues that this finding ran afoul of the Supreme Court’s decision in Shepard v. United States, 544 U.S. 13, 125 S.Ct. 1254, 161 L.Ed.2d 205 (2005), because it was based on impermissible sources.
We need not reach the merits of Salazar-Gonzalez’s Sixth Amendment argument, because Salazar-Gonzalez is entitled to full vacatur of his sentence and a remand for resentencing under United States v. Beng-Salazar, 452 F.3d 1088 (9th Cir.2006), regardless of whether his Sixth Amendment rights were violated.6
In Beng-Salazar, we held that “a defendant who raised an objection in district court based on the Sixth Amendment holdings of the Apprendi line of cases preserved his [nonconstitutional Booker ] claim that he is entitled to resentencing under the advisory Guidelines regime .... unless the Government can show that the error was harmless.” Id. at 1097. Here, as in Beng-Salazar, Salazar-Gonzalez objected to the enhancement of his sentence based on facts that had not been found by a jury beyond a reasonable doubt, namely that his two prior convictions were “unrelated.” In support of his argument, he relied on Blakely v. Washington, 542 U.S. 296, 124 S.Ct. 2531, 159 L.Ed.2d 403 (2004), grounding his objection in the Sixth Amendment right to a jury trial. These objections preserved Salazar-Gonzalez’s claim of nonconstitutional error under United States v. Booker, 543 U.S. 220, 125 S.Ct. 738, 160 L.Ed.2d 621 (2005).
We further hold that the government has not satisfied its burden of demonstrating that the district court’s error was harmless. Indeed, reversal is required even if “we find ourselves ‘in equipoise as to the harmlessness of the error ....’” Beng-Salazar, 452 F.3d at 1096. Because the government cannot point to *860any evidence establishing that it is “more probable than not that the error did not materially affect [Salazar-Gonzalez’s] sentence,” id. at 1092, we VACATE his sentence and REMAND for resentencing under the now-advisory Guidelines.
Conviction AFFIRMED, sentence VACATED and REMANDED.