ON RECONSIDERATION
KENNEY, Judge:Appellant was tried by special court-martial, military judge alone. Pursuant to his pleas of guilty, entered in accordance with a pretrial agreement, Appellant was convicted of one specification of fraudulent enlistment, in violation of Article 83, Uniform Code of Military Justice (UCMJ), 10 U.S.C. § 883; three specifications of wrongfully using cocaine and one specification of wrongfully possessing cocaine, all in violation of Article 112a, UCMJ, 10 U.S.C. § 912a; and one specification of wrongfully possessing a loaded pistol while on board Naval Air Station Corpus Christi, in violation of Article 134, UCMJ, 10 U.S.C. § 934. The military judge sentenced Appellant to confinement for five months, reduction to E-l, and a bad-conduct discharge. The Convening Authority approved the sentence as adjudged except for confinement in excess of ninety days, which was disapproved pursuant to the pretrial agreement.
Before this Court, without admitting that the findings and sentence are correct in law and fact, Appellant submitted this case on its merits as to any and all errors.
On 2 November 2009, this Court set aside the findings on Charge III and its sole specification and dismissed that Charge and Specification, and affirmed the remaining findings of guilty and the approved sentence. The Government moved for reconsideration, and we granted the motion on 8 December 2009. Upon such reconsideration, we affirm our previous decision. The opinion of 2 November 2009 is withdrawn and replaced with the present opinion.
*619Reviewing the record on its merits, we are troubled by the specification of wrongfully possessing a loaded pistol, and the providence inquiry upon this nonstandard specification. The specification reads:
In that Seaman Apprentice Charles A. Hester ... did, at Naval Air Station Corpus Christi, Texas, on or about 30 April 2007, wrongfully possess a loaded pistol while on board the said Naval Air Station Corpus Christi, Texas, such conduct being prejudicial to good order and discipline in the armed forces or being of a nature to bring discredit upon the armed forces.
A Stipulation of Fact, Prosecution Exhibit 1, states that a certain Naval Air Station Corpus Christi directive requires personnel to “ ‘declare weapons being introduced aboard the Naval Air Station at the Security Department and Weapons Division upon arrival,’ ” and that it “prohibits concealed weapons being allowed aboard any naval installation or activity.” (Prosecution Ex. 1 at 5.) It further states that a pistol was found in the back seat of Appellant’s pick-up truck parked on board NAS Corpus Christi, within arm’s distance of the driver’s seat, loaded with a round in the chamber; and that he never notified the Security Department or Weapons Division that he introduced the weapon. (Id. at 6.) It goes on to aver that Appellant “violated naval installation or activity policy when he wrongfully possessed his pistol in a concealed manner, to wit, inside his pick-up truck, as specified in” the directive. (Id.)
During the providence inquiry, Appellant testified that he consented to investigators’ search of his vehicle and retrieval of his pistol, which “was in the back seat of my truck. Laying in the back seat. One of the agents had asked me if my truck was on base before he had searched it, and did I know that it was — that I was in the wrong possessing it on the base, and at the time I was not aware.” (R. at 44.) He acknowledged that the pistol was loaded and that he had never notified the Security Department or the Weapons Division that he had the pistol on board. (R. at 45.) The military judge then explained, “Wrongful means that you had no legal justification or authorization. So in this case you had no legal — did you have any legal or authorization [sic] to possess the loaded pistol on base?” Appellant answered that he did not. (Id.)
The legal standard for determining if a guilty plea is provident is whether the record presents a substantial basis in law or fact for questioning it. United States v. Prater, 32 M.J. 433, 436 (C.M.A.1991); United States v. Inabinette, 66 M.J. 320, 322 (C.A.A.F.2008). The record must contain a sufficient factual basis to support the plea. R.C.M. 910(e). “A military judge’s decision to accept a guilty plea is reviewed for an abuse of discretion.” United States v. Eberle, 44 M.J. 374, 375 (C.A.A.F.1996). “A military judge abuses this discretion if he fails to obtain from the accused an adequate factual basis to support the plea — an area in which we afford significant deference.” Inabinette, 66 M.J. at 322. “The providence of a plea is based not only on the accused’s understanding and recitation of the factual history of the crime, but also an understanding of how the law relates to those facts.” United States v. Medina, 66 M.J. 21, 26 (C.A.A.F.2008) (citing United States v. Care, 18 USCMA 535, 538-39, 40 C.M.R. 247, 250-51, 1969 WL 6059 (1969)). The accused must believe and admit every element of the offense. United States v. Whiteside, 59 M.J. 903, 906 (C.G.Ct.Crim. App.2004) (citing R.C.M. 910(e) Discussion).
Article 134, UCMJ criminalizes three types of conduct: conduct to the prejudice of good order and discipline in the armed forces (clause 1), conduct of a nature to bring discredit on the armed forces (clause 2), and other offenses and crimes not capital (clause 3). Manual for Courts-Martial (MCM), United States (2005 ed.)1, Pt. IV, ¶ 60c(l). The novel specification in Charge III, apparently drafted pursuant to MCM, ¶ 60c(6)(c),2 *620does not appear to implicate any other State or Federal law, thus is not a clause 3 offense, but instead, as drafted, is both a clause 1 and a clause 2 offense. The elements of clause 1 and clause 2 offenses are straightforward:
(1) That the accused did or failed to do certain acts; and
(2) That under the circumstances, the accused’s conduct was to the prejudice of good order and discipline on the armed forces or was of a nature to bring discredit upon the armed forces.
MCM, ¶ 60b.
While the elements of a clause 1 or clause 2 offense are clear, they do not end the inquiry when examining the providence of a guilty plea to a novel specification.
While the elements suggest that Article 134 is a license to create punishable offenses, in fact the creation of novel offenses under clauses 1 and 2 requires careful drafting of the specification to make clear what facts must be proved to warrant conviction_Basic to alleging and proving a punishable offense is the existence and identification of a wrongful act or acts that meet the requirements of either or both of the clausés.
United States v. Henderson, 32 M.J. 941, 947 (N.M.C.M.R.1991) (Lawrence, J., concurring). In a guilty plea, the military judge then must carefully analyze and describe the novel specification to the accused to ensure that the accused understands the law as it relates to the facts. Medina, 66 M.J. at 26.
Under either clause, a servicemember must have or be given adequate notice that his contemplated conduct is punishable. See Parker v. Levy, 417 U.S. 733, 94 S.Ct. 2547, 41 L.Ed.2d 439 (1974). Notice may be shown in different ways. If the act is malum in se, that is, it is inherently wrongful and known to be so by anyone in our society, the notice requirement is met. See United States v. Davis, 26 M.J. 445, 448 (C.M.A.1988). Common law offenses are of this nature as are those crimes found in most of our penal codes. In the military services, certain acts may be inherently wrongful and known to be so by any reasonable servicemember due to their occurrence in the military context, even though they are not prohibited in the civilian sector. See id. [cross-dressing]; United States v. Lowe, 4 U.S.C.M.A. 654, 16 C.M.R. 228, 1954 WL 2445 (1954)[public and private drunkenness]. If the act is malum prohibitum, that is, wrong because it is prohibited by regulation, order, or even policy, the notice requirement may be met if the proscription applies to the accused. Of course, if this is the basis for prosecution the existence of the regulation, order, or policy statement and its applicability to the accused must be proved as an essential element of the offense.
Henderson, 32 M.J. at 947-48.
The novel specification in this case appears to have been drafted and prosecuted on the general theory that rules (such as those found in the Naval Air Station directive) not amounting to a lawful general order and not providing a basis for a specification of dereliction of duty with respect to a certain accused can nevertheless make conduct by that accused “wrongful” and thereby serve as the basis of criminal liability as malum prohibi-tum under the General Article. The Government’s basis of prosecution under this theory appears to be that the Naval Air Station policy prohibited the introduction of weapons onto the base without authorization, that the policy applied to Appellant, that Appellant violated that policy, and that violating the policy was wrongful, regardless of any knowledge of its existence.
Given that the Government’s theory of prosecution is contained in a novel specification, it was essential for the military judge to conduct a careful examination to ensure that Appellant understood the theory. Medina, 66 M.J. at 26. However, the record does not reveal that Appellant understood the Government’s theory of prosecution.3
*621The providence inquiry failed to establish a factual basis for wrongfulness. There was no inquiry on whether the Naval Air Station directive applied to Appellant and the directive itself is not contained in the record of trial. The directive appears to be the basis for the allegation that Appellant’s conduct was wrongful. Yet without indication that it applied to him or that he should have known of its provisions and complied with them, we do not see how it can be said that his conduct was wrongful, as the specification alleges.4 There is nothing about the conduct itself that is obviously wrongful (i.e., malum in se5), nor is there any indication that Appellant had notice that it was wrongful (i.e., malum pro-hibitum). The Government claims Appellant’s conduct violated military custom, citing United States v. Vaughan, 58 M.J. 29 (C.A.A.F.2003). However, the Vaughan finding of a military custom was supported by several Department of Defense directives. Here, the Government cites noting more substantial than the Naval Air Station Corpus Christi directive mentioned above and a newspaper article. Furthermore, the Government provides no support for a Coast Guard custom. To be the basis for a charge, military custom must be a custom of the military service of which the accused is a member. See United States v. Johanns, 20 M.J. 155, 157-58 (C.M.A.1985). As for state statutes and military case law that may contribute to notice of wrongfulness of certain conduct, Vaughan, 58 M.J. at 31-32, the Government’s disparate examples do not align with Appellant’s alleged conduct, and thus provide no clear picture that Appellant’s conduct was wrongful. In sum, although Appellant admitted that his conduct was wrongful, we discern no factual basis for this element of the offense.
We need not reach the question of whether the specification was legally sufficient.6 This case turns on the providence inquiry.
As noted, Appellant indicated that he believed and admitted his guilt, but there is not an adequate factual basis for the essential element of wrongfulness. The military judge, when addressing the wrongfulness element of the offense, merely stated: “Wrongful means that you had no legal justification or authorization. So in this ease you had no legal — did you have any legal or authorization [sic] to possess the loaded pistol on base?” (R. at 45.) This simple inquiry is better suited towards an offense that is ma-lum in se. For a malum prohibitum offense contained in a novel specification, more is needed. Accordingly, we hold that the military judge abused his discretion when he accepted the guilty pleas for the Article 134, UCMJ offense.
We set aside the finding of guilty of Charge III and its specification, the weapon offense. Having done so, we may affirm only so much of the sentence as we believe the military judge would have adjudged in the absence of the finding we are setting aside; if we are unable to determine what that would have been, we must order a rehearing on sentence. United States v. Sales, 22 M.J. 305, 307 (C.M.A.1986). In this case, we are certain that without Charge III, the military judge would have adjudged a sentence not less than the sentence that was approved by the Convening Authority.
Decision
We have reviewed the record in accordance with Article 66, UCMJ, 10 U.S.C. § 866. Upon such review, the findings on Charge III and its sole specification are set aside and the Charge and Specification are dismissed. The remaining findings of guilty are determined to be correct in law and fact and, on the basis of the entire record, should be approved. Accordingly, those findings of guilty are affirmed. The approved sentence of confinement for ninety days, reduction to *622E-l, and a bad-conduct discharge is affirmed.
Chief Judge MCCLELLAND and Judge LODGE concur.. Appellant’s offenses took place between April 2006 and July 2007. The provisions of the MCM cited in this opinion are identical in the 2005 and 2008 editions.
. ¶ 60c(6)(c) states: "Specifications for clause 1 or 2 offenses not listed. If conduct by an accused does not fall under any of the listed offenses for violations of Article 134 in this Manual (paragraphs 61 through 113 of this Part) a specifica*620tion not listed in this Manual may be used to allege the offense."
. The Government argues that Appellant acknowledged the danger of his conduct, but that is not the same as understanding its criminality. Other theories urged upon us by the Government were not discussed with Appellant at trial.
. This allegation was necessary for a legally sufficient specification.
. The Government asserts that the conduct was malum in se based on common proscription, but we are not persuaded.
. Since the Naval Air Station directive was not included in the record, we also refrain from speculating on why the offense alleged was not charged under Article 92, UCMJ, 10 U.S.C. § 892. But we are certain that the "preemption doctrine” in MCM, 2005, ¶ 60c(5)(a) which “prohibits application of Article 134 to conduct covered by Articles 80 through 115” would not apply in this case, regardless.