  For a fixed positive integer n, let S_n denote the symmetric group of n!
permutations on n symbols, and let maj(sigma) denote the major index of a
permutation sigma. For positive integers k<m not greater than n and
non-negative integers i and j, we give enumerative formulas for the cardinality
of the set of permutations sigma in S_n with maj(sigma) congruent to i mod k
and maj(sigma^(-1)) congruent to j mod m. When m divides n-1 and k divides n,
we show that for all i,j, this cardinality equals (n!)/(km).
