Izua Dictionary(AOJ No.0271)

nと、0, 1, ..., n-1を並べ替えてできるn!個の数列が辞書に乗っている。
数列0, 1, ..., n-1を入力に従ってR回スワップしてできた数列 $x_0, x_1, \cdots x_{n-1}$ が辞書の何番目に乗っているかを答える。
ただし、0, 1, ..., n-1は、0番目に乗っていると数える。
答えは,大きな数になりうるので1,000,000,007の剰余で答える。
制約
1 ≤ n ≤ 100000 = N
0 ≤ R ≤ 50

アルゴリズム

先頭から１文字筒注目し、辞書順で何番目かを求め、総和を求める。
$\sum_{i=0}^{n-1} (x_i - \sum_{j < i, x_j < x_i}1)(n-1-i)!$ 　　 $\pmod{1,000,000,007}$
あんま上手く説明できないけど、
(n-1-i)!がi番目より後ろの並べ方。係数は0から $x_i$ の中ですでに使用したものを除いたアルファベットの候補数。
(n-1-i)!は階乗のテーブルを始めに使っておき、
$\sum_{j < i, x_j < x_i}1$ はbinary indexed treeを使用すれば低コストで計算できる。

コード

import java.util.*;
public class aoj0271 {
    static final Scanner stdin = new Scanner(System.in);
    static final int MOD = 1000000007, NMAX = 100001, seq[] = new int[NMAX], input[] = new int[NMAX];
    static final long factMod[] = new long[NMAX];
    static {
        factMod[0] = 1;
        for (int i = 1; i < NMAX; ++i) {
            factMod[i] = (factMod[i-1]*i) % MOD;
            seq[i] = i;
        }
    }
    public static void main(String[] args) {
        while (true) {
            int N = stdin.nextInt();
            if (N == 0) break;
            FenwickTree BIT = new FenwickTree(N+1);
            System.arraycopy(seq, 0, input, 0, N);
            int R = stdin.nextInt();
            while (R-- > 0) {
                int a = stdin.nextInt()-1, b = stdin.nextInt()-1;
                int tmp = input[a]; input[a] = input[b]; input[b] = tmp;
            }
            long ans = 0;
            for (int i = 0; i < N; i++) {
                int cnt = input[i] - BIT.sum(input[i]);
                ans = (ans + cnt * factMod[N-i-1]) % MOD;
                BIT.add(input[i], 1);
            }
            System.out.println(ans);
        }
    }
    public static class FenwickTree {
        private int[] x;
        public FenwickTree(int n){ init(n);}
        public final void init(int n){ x = new int[n]; Arrays.fill(x, 0); }
        public final int sum(int i){
            int ret = 0;
            for(int j = i; j >= 0; j = ((j & (j+1)) - 1)) ret += x[j];
            return ret;
        }
        public final void add(int i, int a){
            for(int j = i; j < x.length; j |= j+1) x[j] += a;
        }
    }
}