Permutation Order I

Let $\mathfrak{S}(n)$ be the set of all permutations of [1..n]

The order of a permutation $\mathfrak{p}$ is the smallest integer e such as ${\mathfrak{p}}^e=Id$
We apply the permutation e times to itself and get the identity permutation {1,2,...,n}

For $\mathfrak{S}(4)$ :

 Order(1 2 3 4) = 1
 Order(1 2 4 3) = 2
 Order(1 3 2 4) = 2
 Order(1 3 4 2) = 3
 Order(1 4 2 3) = 3
 Order(1 4 3 2) = 2
 Order(2 1 3 4) = 2
 Order(2 1 4 3) = 2
 Order(2 3 1 4) = 3
 Order(2 3 4 1) = 4
 Order(2 4 1 3) = 4
 Order(2 4 3 1) = 3
 Order(3 1 2 4) = 3
 Order(3 1 4 2) = 4
 Order(3 2 1 4) = 2
 Order(3 2 4 1) = 3
 Order(3 4 1 2) = 2
 Order(3 4 2 1) = 4
 Order(4 1 2 3) = 4
 Order(4 1 3 2) = 3
 Order(4 2 1 3) = 3
 Order(4 2 3 1) = 2
 Order(4 3 1 2) = 4
 Order(4 3 2 1) = 2

What is the largest order for the elements of $\mathfrak{S}(85)$?
For which permutation do we get this order? Give the index in lexicographic order (0-origin) of the 1st one

Answer format: Maximal order,Index modulo ${10}^9$

Example: 420,257453673 // For $\mathfrak{S}(20)$

[My timing: 40 sec]