OPINION
{1} In this appeal regarding a taxpayer’s protest of the assessment of gross receipts taxes to the sale of services, the painting of airplanes, to out-of-state customers, we address the requirement for a deduction under NMSA 1978, § 7-9-57(A) (2000), that the buyer not make initial use or take delivery of the product of the service in New Mexico. We conclude that the flying of an airplane to the customer’s out-of-state location for in*190spection and acceptance of the service does not constitute initial use. We nonetheless conclude that Taxpayer, Dean Baldwin Painting, Inc., did not meet its burden of proof to show out-of-state delivery that would permit Taxpayer to take the deduction. We affirm the denial of the protest.
BACKGROUND
{2} Taxpayer filed a timely protest of an assessment of gross receipts taxes by the New Mexico Taxation and Revenue Department (TRD). The following facts were determined by the TRD hearing officer after hearing.
{3} During the audit period in question, April 1998 through June 2001, Taxpayer engaged in the business of painting airplanes used by airlines, corporations, cargo companies, and the United States military. It operated a facility in New Mexico, and it performed all work that is the subject of the protest at the facility. Flight crews of customers flew the customers’ airplanes to and from Taxpayer’s New Mexico facility. They did so under Federal Aviation Administration (FAA) “ferry permits” that permit transport to and from a specified maintenance location without the presence of paying customers or cargo. Typically, the crews were maintenance crews that fly the airplanes for maintenance only, rather than the customers’ regular flight crews. Customers’ technical representatives often remained with the airplanes to act as liaisons with Taxpayer.
{4} The customers retained title to the airplanes. Taxpayer’s mechanics had FAA certifications to inspect the airplanes for safety to fly after painting, but they could not recertify the airplanes to carry paying passengers or cargo. That necessary recertification took place after the customers’ flight crews transported the airplanes to another location for inspection, including inspection of Taxpayer’s work. If a customer had a complaint, Taxpayer would perform additional work either at its New Mexico facility or at the customer’s location.
{5} The hearing officer concluded that Taxpayer’s customers both made initial use of and took delivery of the product of Taxpayer’s service in New Mexico. The hearing officer therefore denied Taxpayer’s protest except for an amount that is not at issue in this appeal. Taxpayer appeals, contending that it is entitled to deductions from its gross receipts for its receipts from all customers except the two with which it had a services agreement because it provided the services to an out-of-state customer under Section 7-9-57(A).
APPLICATION OF SECTION 7-9-57(A)
{6} Section 7-9-57(A) provides:
Receipts from performing a service may be deducted from gross receipts if the sale of the service is made to an out-of-state buyer who delivers to the seller either an appropriate nontaxable transaction certificate or other evidence acceptable to the secretary unless the buyer of the service or any of the buyer’s employees or agents makes initial use of the product of the service in New Mexico or takes delivery of the product of the service in New Mexico.
The language of Section 7-9-57(A) is clear. To be entitled to a deduction, neither of the conditions that would negate the deduction can exist; the buyer of the service can neither make initial use in New Mexico nor take delivery in New Mexico. We address each condition to determine if it applies in this case.
I. Initial Use in New Mexico
{7} The product of the service must be used initially outside New Mexico if the receipts from the provision of the service are to be deducted from the receipts of a taxpayer providing services within New Mexico. Section 7-9-57(A). The hearing officer concluded that Taxpayer’s customers made initial use of their painted airplanes in New Mexico. We review the hearing officer’s conclusion concerning the application of Section 7-9-57(A) de novo because it presents a question of law. See TPL, Inc. v. N.M. Taxation & Revenue Dep’t, 2003-NMSC-007, ¶ 10, 133 N.M. 447, 64 P.3d 474.
{8} The hearing officer relied upon Reed v. Jones, 81 N.M. 481, 468 P.2d 882 (Ct.App.1970). In that case, the taxpayer performed repairs on his customer’s bread delivery truck in New Mexico. Id. at 481-82, 468 *191P.2d at 882-83. Upon completion of the work, the truck was driven to Texas, where the customer was located. Id. at 482, 468 P.2d at 883. We held that initial use was made of the truck in New Mexico, rather than in Texas, where it would be placed in service for bread deliveries. Id. We stated that if the statute had been clear, we would not have needed to construe the language “initial use.” Id. at 482-83, 468 P.2d at 883-84. Since the issuance of the Reed opinion, the legislature has defined “initial use.” NMSA 1978, § 7-9-3(0) (1991, as amended through 2002) (current version at NMSA 1978, § 7-9-3(D) (2006)). We are therefore guided by the statutory definition rather than the interpretation in Reed.
{9} Section 7-9-3(D) defines “initial use” as “the first employment for the intended purpose.” The product of Taxpayer’s service was a repainted airplane. See TPL, 2003-NMSC-007, ¶ 12, 133 N.M. 447, 64 P.3d 474 (stating that “the ‘product’ is the ‘direct result’ or ‘consequence’ flowing from the service” and that the benefit received represents the “product of service”). The intended purpose of the airplanes, depending on the customer, was to transport passengers or cargo, or to conduct activity of the military.
{10} The transport by the customers’ maintenance crews was not a use for the airplanes’ intended purpose. The customers’ maintenance crews transported the airplanes to and from New Mexico for the limited purpose of maintenance under an FAA permit restricting the use of the airplane. The transport by a maintenance crew from Taxpayer’s facility to the location selected by the customer was merely an extension of the maintenance of the airplane. It may have enabled the customer to return the airplane to its intended use or purpose, but the airplane still needed to be inspected and recertified before it could again be used for its intended purpose. This inspection and re-certification did not take place in New Mexico. The first employment of the airplane for its intended purposes, therefore, could not have occurred until the airplane was transported from New Mexico. The hearing officer was incorrect in concluding that there was initial use in New Mexico.
II. Delivery in New Mexico
{11} A valid deduction from gross receipts under Section 7-9-57(A) also requires that delivery not occur in New Mexico. Taxpayer argued at the TRD hearing, as it does on appeal, that even though the customers took physical possession in New Mexico, delivery did not take place until the customers inspected the airplanes and accepted delivery of the product of the service, which occurred after inspection outside New Mexico. The hearing officer concluded that Taxpayer’s customers took delivery at Taxpayer’s facility in New Mexico. The hearing officer reasoned that (1) there was no legal authority equating delivery and acceptance, and (2) there was an absence of proof to support Taxpayer’s argument. Because we believe that Taxpayer did not meet its burden of proof, we do not address the hearing officer’s first ground.
{12} A taxpayer has the burden of proof when claiming entitlement to a deduction from tax. TPL, 2003-NMSC-007, ¶ 31, 133 N.M. 447, 64 P.3d 474. There is a statutory presumption that “all receipts of a person engaging in business are subject to the gross receipts tax.” NMSA 1978, § 7-9-5(A) (2002). There is a separate statutory presumption that a TRD tax assessment is correct. NMSA 1978, § 7-l-17(C) (1992). When a taxpayer claims an exemption or deduction from a tax, strict rules of construction structure a court’s analysis: (1) the court must construe the statute allowing the exemption or deduction in favor of the taxing authority; (2) the statute must clearly and unambiguously express the right to the exemption or deduction; and (3) the taxpayer must clearly establish the right to the exemption or deduction. Sec. Escrow Corp. v. State Taxation & Revenue Dep’t, 107 N.M. 540, 543, 760 P.2d 1306, 1309 (Ct.App.1988); see TPL, 2003-NMSC-007, ¶ 9, 133 N.M. 447, 64 P.3d 474 (“The taxpayer must show that it is clearly entitled to the statutory deduction.”). Additionally, the taxpayer has the obligation to “maintain books of account or other records in a manner that will permit the accurate computation of state taxes.” NMSA 1978, § 7-l-10(A) (2001).
*192{13} Our analysis of Taxpayer’s obligation to meet its burden of proof necessitates that we examine Taxpayer’s evidence brought to TRD. TRD assessed gross receipts taxes against Taxpayer based on receipts of sixteen customers. Taxpayer produced documentation concerning the agreement with four of these customers for five separate jobs. For two customers, Taxpayer produced services agreements: SkyWest Airlines, dated April 1, 1999, and Pinnacle Air Cargo Enterprises, Inc., dated April 8, 1999. Each of these services agreements specified that delivery and redelivery took place at Taxpayer’s New Mexico facility. Each services agreement required Taxpayer to provide on-site office space for the customer’s technical representatives, who had the authority to accept performance of the services and redelivery. Under the service agreement, Taxpayer would submit the airplanes to the customers at redelivery for an inspection and a test flight. In addition to the services agreements with SkyWest and Pinnacle, Taxpayer produced two written proposals to other customers for its services. Each of these proposals referenced and contemplated a services agreement, but no such agreement was produced. Taxpayer also produced a proposal to SkyWest dated August 27, 1999.
{14} Taxpayer stipulated that SkyWest and Pinnacle took delivery of the airplanes at its New Mexico facility under the services agreements and that gross receipts tax was due on the receipts for these jobs. For SkyWest, the stipulation covered the period from April 1, 1999, the date of the services agreement, to August 27, 1999, the date of Taxpayer’s proposal to SkyWest. Taxpayer had $1,078,885.28 in receipts from SkyWest during the audit period, and the stipulation addressed $261,778 of the total, leaving unresolved the remainder of the receipts from before and after the stipulation period.
{15} Taxpayer’s CEO and majority owner testified at the TRD hearing. The CEO stated that it was Taxpayer’s understanding that delivery did not occur until after acceptance of the work. The CEO testified that, other than for the work performed under the SkyWest and Pinnacle services agreements, the airplanes went to the customers’ facilities outside New Mexico for inspection and acceptance. She said that, except for deposits, Taxpayer did not bill for its services until after completion of the work. The CEO did not remember the services agreements and believed that a former marketing employee had used them. She stated that the contract that Taxpayer used beginning in October 1999 was a form of the written proposals that were in evidence with an acceptance provision on the form. She further stated that many times Taxpayer did not receive signed copies back before doing the work.
{16} The hearing officer did not find the CEO’s testimony to be credible based on inconsistencies between the CEO’s testimony and the documentary evidence and the CEO’s admitted lack of knowledge and memory. By way of example, the hearing officer pointed to the SkyWest work to demonstrate inconsistencies. The CEO stated that the reason the SkyWest services agreement designated Taxpayer’s New Mexico facility for delivery to SkyWest was that under the services agreement SkyWest sent technicians with their airplanes who were capable of accepting delivery, while the later technicians receiving the airplanes did not have that capability. According to the CEO, SkyWest did so because Taxpayer was newly operating under an FAA license at the time of the services agreement. The hearing officer noted, however, that before the services agreement, Taxpayer had already received $254,448 for work performed for SkyWest. Additionally, without explanation, Taxpayer maintained that the delivery of the earlier work did not take place in New Mexico.
{17} The hearing officer also observed the lack of clarity and support for Taxpayer’s position in the written proposals of record. Each of the proposals referred to paint services agreements. Taxpayer’s CEO could not explain these references, and Taxpayer did not produce any such agreements. Nor could Taxpayer produce any documentation pertaining to agreements with the remainder of Taxpayer’s customers during the audit period. The hearing officer concluded that *193Taxpayer did not provide credible evidence that delivery took place outside New Mexico.
{18} Our review of a TRD appeal is subject to the strictures of administrative review. We may reverse only if the decision and order of the hearing officer is
(1) arbitrary, capricious or an abuse of discretion;
(2) not supported by substantial evidence in the record; or
(3) otherwise not in accordance with the law.
NMSA 1978, § 7-l-25(C) (1989). Taxpayer essentially argues that the hearing officer’s decision and order is not supported by substantial evidence in the record and is contrary to the law as established in TPL. In reviewing for substantial evidence, we must examine the record as a whole, including evidence both supporting and contravening the administrative decision. See Carlsberg Mgmt. Co. v. State, Taxation & Revenue Dep't, 116 N.M. 247, 249, 861 P.2d 288, 290 (Ct.App.1993). We review for adherence to law de novo. See Grogan v. N.M. Taxation & Revenue Dep’t, 2003-NMCA-033, ¶ 10, 133 N.M. 354, 62 P.3d 1236.
{19} Our review of the record as a whole reveals substantial evidence to support the decision and order. There was no dispute that customers’ crews took physical possession of the painted airplanes at Taxpayer’s New Mexico facility and transported them to customers’ locations outside New Mexico. The issue for the hearing officer was whether Taxpayer met its burden of proof that Taxpayer was entitled to a deduction from gross receipts because Taxpayer did not make delivery of the airplanes in New Mexico because the customers agreed otherwise. Taxpayer presented testimony that it understood that its customers did not take delivery until Taxpayer’s services were accepted after inspection outside New Mexico. However, the only documentation of agreements it had with customers, two paint services agreements, expressly stated to the contrary. Moreover, the only other documentation Taxpayer had bearing on agreements with customers, three written proposals, expressly contemplated a further agreement, which by name was the same agreement that provided that delivery was to occur at Taxpayer’s facility in New Mexico. Although two of the proposals stated that gross receipts tax will be added if the departing flight after paint work did not terminate outside New Mexico, this statement does not directly address the determinative issue of delivery.
{20} Taxpayer’s CEO tried to explain the inconsistencies. She testified that Taxpayer’s written agreements since October 1999 consisted of proposals with an acceptance provision on the document. Yet, Taxpayer did not produce any such agreements. In its briefing on appeal, Taxpayer asserts that it also acted under oral contracts. The CEO’s testimony establishes that Taxpayer did not always have written contracts and at times would perform services after it sent an unreturned written proposal to a customer. However, except to state her understanding about the terms of delivery in the general sense, the CEO did not testify to any specific oral agreement with any particular customer.
{21} Taxpayer additionally argues on appeal that it did not deliver airplanes to its customers until after inspection and acceptance at its customers’ locations because it retained the risk of loss until that time. Although Taxpayer’s CEO testified that she most likely would not charge a customer if an airplane crashed and was destroyed en route to the customer’s location, she stated that she had not previously considered the circumstance and did not state that the risk of loss was defined in the agreements with customers. The CEO also testified that if Taxpayer’s work is not accepted, a customer would send it back or Taxpayer would send a technician to the customer’s location for repair. As the hearing officer concluded, this subsequent work by Taxpayer was consistent with Taxpayer’s warranty obligation as expressed in the paint services agreements and proposals that were produced.
{22} In the performance of all of its services in the audit period, Taxpayer gave possession to its customers in New Mexico. Taxpayer bears the burden of establishing the deductions and therefore had the burden to demonstrate that delivery did not occur in New Mexico. It has the obligation to main*194tain records supporting the accuracy of the computation of its taxes. For the most part, Taxpayer did not produce documents pertaining to the delivery of its customers’ airplanes. The only clear documents it produced indicated that delivery took place in New Mexico. The other documents, as well as the testimony of Taxpayer’s CEO, tended to show that additional relevant documents existed at one time, but were not produced. In addition to the lack of documentation, the hearing officer did not find the CEO’s testimony to be credible and pointed to inconsistencies in her testimony. We defer to such a finding unless it is not “supported by substantial evidence on the record as a whole.” Herman v. Miners’ Hosp., 111 N.M. 550, 552, 807 P.2d 734, 736 (1991). We are satisfied that substantial evidence exists in the whole record that Taxpayer did not meet its burden.
{23} With substantial evidence supporting the hearing officer’s decision and order, we consider whether the decision and order is arbitrary, capricious, or an abuse of discretion, or otherwise contrary to law. Because there is a “rational connection between the facts found and the choices made,” the hearing officer’s decision is not arbitrary or capricious. Regents of the Univ. of Cal. v. N.M. Water Quality Control Comm’n, 2004-NMCA-073, ¶ 35, 136 N.M. 45, 94 P.3d 788 (internal quotation marks and citation omitted). It is not contrary to law because the hearing officer followed the law regarding a taxpayer’s burdens to establish entitlement to a deduction from tax and to maintain proper records. It is not an abuse of discretion both because there was substantial evidence in its support and because the hearing officer followed the law.
{24} Taxpayer additionally argues that the similarity of this case to TPL requires reversal. In TPL, a New Mexico corporation received munitions from another state and “demilitarized” and disposed of them in New Mexico, in accordance with its customer’s instructions. TPL, 2003-NMSC-007, ¶¶2, 25, 133 N.M. 447, 64 P.3d 474. Our Supreme Court held that the corporation met its burden of proof entitling it to a deduction from the gross receipts tax. Id. ¶ 32. Taxpayer bases its argument on three statements in TPL. Our Supreme Court stated that if the New Mexico corporation had worked on the munitions and then shipped them back to its customer out-of-state, it would be clear that the customer took delivery and made initial use in its home state. Id. ¶25. It stated that an “out-of-state buyer does not automatically make initial use or take delivery of services within New Mexico when services are performed upon its personal property sent to New Mexico.” Id. ¶ 23. It further stated that “the buyer must perform some identifiable activity within the state that constitutes initial use or acceptance of delivery.” Id. Taxpayer argues from these statements that it “should not be penalized because it is providing a service involving personal property that is too large to be packaged up in a box and shipped back to the customer.”
{25} We do not disagree with the principle that delivery of personal property such as an airplane that has received service in New Mexico need not take place in New Mexico. However, TPL does not change our result because we base our decision on the record in this case and on Taxpayer’s failure to meet its burden of proof that delivery of its services took place outside New Mexico. Moreover, this case differs from TPL because Taxpayer’s customers were present in New Mexico to accept physical possession of the airplanes and such transfer of physical possession could be factually construed to constitute acceptance of delivery.
{26} Nor do we disagree with Taxpayer’s statement of the policy considerations of Section 7-9-57(A) that seek to eliminate a competitive disadvantage for New Mexico businesses that are subject to gross receipts tax on services not imposed in all other states. See TPL, 2003-NMSC-007, ¶¶20, 30, 133 N.M. 447, 64 P.3d 474. Again, Taxpayer must demonstrate that it is entitled to a deduction, and the hearing officer concluded otherwise based on substantial evidence.
CONCLUSION
{27} We reverse the hearing officer’s conclusion that the deduction does not apply because the customers made initial use of their airplanes in New Mexico. We affirm the hearing officer’s conclusion that the de*195duction does not apply because delivery was effected in New Mexico, and we therefore affirm the denial of Taxpayer’s protest.
{28} IT IS SO ORDERED.
WE CONCUR: JONATHAN B. SUTIN, Chief Judge, and A. JOSEPH ALARID, Judge.