ld calc_dp1(int i, int j) {
    if (dp1[i][j]!=-1) return dp1[i][j];
    int tmp_j = j;
    for (int k=0;k<i;k++) {
        tmp[k] = tmp_j % i;
        tmp_j /= i;
    }

    int cnt_forward = 0;
    ld kek = 0;
    for (int k=0;k<i;k++) {
        for (int l=0;l<i;l++) {
            if (tmp[k]<=tmp[l]) {
                kek++;
            } else {
                for (int m=0;m<i;m++) {
                    tmp2[m] = tmp[m];
                }
                swap(tmp2[k], tmp2[l]);
                int lkek = 0;
                for (int m=i-1;m>=0;m--) {
                    lkek *= i;
                    lkek += tmp2[m];
                }
                kek+=calc_dp1(i, lkek);
                cnt_forward++;
            }
        }
    }

    if (cnt_forward==0) {
        return dp1[i][j] = 0;
    }

    return dp1[i][j] = kek/cnt_forward;
}