United States Court of Appeals
                           FOR THE EIGHTH CIRCUIT
                                   ___________

                                   No. 05-1821
                                   ___________

Kenneth E. Batchelder,                  *
                                        *
             Appellant,                 *
                                        * Appeal from the United States
      v.                                * District Court for the
                                        * District of Nebraska.
INS; DHS; FCI; DOJ; EEOC,               *
                                        *   [UNPUBLISHED]
             Appellees.                 *
                                   ___________

                             Submitted: May 1, 2006
                                Filed: May 11, 2006
                                 ___________

Before MELLOY, FAGG, and BENTON, Circuit Judges.
                           ___________

PER CURIAM.

       Kenneth Batchelder appeals following the district court’s dismissal with
prejudice of his suit alleging employment discrimination under Title VII and the
Rehabilitation Act. We disagree with the court’s sua sponte dismissal of the
complaint for a failure to exhaust administrative remedies, because Batchelder was not
provided notice prior to dismissal that he had to provide evidence of exhaustion. See
Ballard v. Rubin, 

, 964 n.6 (8th Cir. 2002) (exhaustion under
Rehabilitation Act is not jurisdictional prerequisite, but is requirement subject to
waiver, estoppel, and equitable tolling); Shempert v. Harwick Chem. Corp., 

, 797 (8th Cir. 1998) (same for Title VII), cert. denied, 

(1999). We
also need not determine whether the court’s alternate ground for dismissal--defects in
service of process--are excused by the requirements of 28 U.S.C. § 1915(d) (officers
of court “shall issue and serve all process, and perform all duties” in cases where
plaintiffs are proceeding IFP), because Batchelder’s largely unintelligible and
incomprehensible allegations fail to provide fair notice of his claims and the grounds
upon which they rest. See Jones v. United States, 

, 511 (8th Cir. 2001)
(appeals court may affirm district court on any basis supported by record); cf.
Swierkiewicz v. Sorema N.A., 

, 514-15 (2002) (to state claim under Title
VII, plaintiff must provide fair notice of claim and grounds upon which it rests);
Martin v. Sargent, 

, 1337 (8th Cir. 1985) (pro se complaint must contain
specific facts supporting its conclusions).

      Accordingly, we affirm. We modify the dismissal, however, to be without
prejudice so Batchelder is not precluded from refiling. See 28 U.S.C. § 2106 (appeals
court may affirm, modify, vacate, set aside, or reverse any judgment or order of court
lawfully brought before it for review). We also deny Batchelder’s motion for costs
on appeal.
                       ______________________________




                                         -2-