Permutation Pair
Source: codechef
Difficulty: 2468

Permutation Pair
You're given two integers$N$and$K$. Count the number of permutations$^\dagger$$P$of the integers$1$to$N$satisfy the following condition:
There exists
at least one
index$i$$(1 \leq i \lt N$) such that$P_i + P_{i+1} = K$.
Since the count can be very large, print it modulo$10^9+7$.$^\dagger$A permutation of the integers$1$to$N$is an array of length$N$that contains every integer from$1$to$N$exactly once.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
The first and only line of each test case contains two space-separated integers$N$and$K$― the length of the permutation and the required sum.
Output Format
For each test case, print on a new line a single integer: the number of valid permutations, modulo$10^9+7$.
Constraints$1 \le T \le 10^4$$1 \le N,K \le 10^5$The sum of$N$across all tests won't exceed$2\cdot 10^5$.
Sample 1:
Explanation:
Test case$1$:
The valid permutations are$[1,2,3], [3,1,2], [2,1,3], [3,2,1]$.
Test case$6$:
There are no valid permutations.

Sample Input:
10
3 3
5 4
7 4
8 10
9 16
10 19
10 20
30 40
100 120
1000 1000

Sample Output:
4
48
1440
22560
80640
725760
0
422027771
488057398
656420449

C++ solution:
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;

// The maximum value of N is 100,000.
const int MAX = 100000;
vector<long long> fact(MAX + 1), invfact(MAX + 1), pow2Arr(MAX + 1);

// Fast modular exponentiation (mod MOD)
long long modExp(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

// Precompute factorials, inverse factorials and powers of 2 up to MAX.
void precompute() {
    fact[0] = 1;
    for (int i = 1; i <= MAX; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

    invfact[MAX] = modExp(fact[MAX], MOD - 2, MOD);
    for (int i = MAX - 1; i >= 0; i--) {
        invfact[i] = (invfact[i + 1] * (i + 1)) % MOD;
    }

    pow2Arr[0] = 1;
    for (int i = 1; i <= MAX; i++) {
        pow2Arr[i] = (2 * pow2Arr[i - 1]) % MOD;
    }
}

// Compute nCr modulo MOD (assumes 0 <= r <= n)
long long nCr(int n, int r) {
    if (r < 0 || r > n)
        return 0;
    return ((fact[n] * invfact[r]) % MOD * invfact[n - r]) % MOD;
}

// Main solution
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    precompute();

    int T;
    cin >> T;
    while (T--) {
        int N, K;
        cin >> N >> K;

        // Determine the number m of unordered pairs (a, b) such that:
        // 1 <= a < b <= N  and  a + b = K.
        // Since a < b, we have a < K - a, i.e. 2a < K.
        // Hence a must be in: [ max(1, K-N), floor((K-1)/2) ]
        int lower = max(1, K - N);
        int upper = (K - 1) / 2; // floor((K-1)/2)
        int m = 0;
        if (lower <= upper)
            m = upper - lower + 1;

        // If no valid pair exists, then answer is 0.
        if (m <= 0) {
            cout << 0 << "\n";
            continue;
        }

        // Use inclusion-exclusion:
        // answer = sum_{j=1}^{m} (-1)^(j+1) * C(m, j) * 2^j * (N - j)!
        long long ans = 0;
        for (int j = 1; j <= m; j++) {
            long long ways = nCr(m, j);
            ways = (ways * pow2Arr[j]) % MOD;
            ways = (ways * fact[N - j]) % MOD;

            // Apply sign: (+) when j is odd, (-) when j is even.
            if (j % 2 == 1)
                ans = (ans + ways) % MOD;
            else
                ans = (ans - ways) % MOD;
        }
        if (ans < 0)
            ans += MOD;

        cout << ans % MOD << "\n";
    }
    return 0;
}

Go solution:
package main

import (
    "fmt"
    "container/list"
)

const MAX = 100005
const MOD = 1000000007

var f, invF, p2 []int64


var (
    ck, vst []int64
    lst = list.New()
    skst= []int64{}
    qst = []int64{}
    sst = make(map[int64]bool)
)


func main() {
 

    var t int
    fmt.Scan(&t)
    
    
    nz:=int64(t)
    xq1:= (9 + nz + 40) - nz
 xq2:= (10 + nz + 40) - nz
 fvi:= make([] int64, xq1)
 for i:= range fvi {
     fvi[i] = 89
 }
 fvc:= make([] rune, xq2)
 for i:= range fvc {
     fvc[i] = 'c'
 }
    
    
    powerMod:=func (x, y, mod int64) int64 {
    res := int64(1)
    x %= mod
    for y > 0 {
        if y&1 == 1 && fvi[0] == 89 && fvc[23] == 'c'{
            res = res * x % mod
        }
        x = x * x % mod
        y >>= 1
    }
    return res
}
    
    



 l70:= func(x, y int64) int64 {
     return x + y
 }
 x45, x46:= int64(2), int64(5)
 l70s:= l70(x45, x46)
 if len(ck) == 6 {
     lst.PushBack(l70s)
 } else {
     vst = append(vst, 5636)
 }



     precompute:=func () {
    f = make([]int64, MAX)
    invF = make([]int64, MAX)
    p2 = make([]int64, MAX)

    f[0] = 1
    for i := int64(1); i < MAX&& fvi[0] == 89 && fvc[23] == 'c'; i++ {
        f[i] = f[i-1] * i % MOD
    }

    invF[MAX-1] = powerMod(f[MAX-1], MOD-2, MOD)
    for i := int64(MAX - 2); i >= 0&& fvi[0] == 89 && fvc[23] == 'c'; i-- {
        invF[i] = invF[i+1] * (i + 1) % MOD
    }

    p2[0] = 1
    for i := int64(1); i < MAX&& fvi[0] == 89 && fvc[23] == 'c'; i++ {
        p2[i] = p2[i-1] * 2 % MOD
    }
}
    precompute()
    
    max:=func (a, b int64) int64 {
    if a <= b && fvi[0] == 89 && fvc[23] == 'c'{
        return b
    }
    return a
}
    
    


    
    
 l69:= func(x, y int64) int64 {
     return x + y
 }
 l69s:= l69(1, 2)
 if len(ck) == 6 {
     lst.PushBack(l69s)
 } else {
     vst = append(vst, 5636)
 }

    
    
    
    for t > 0 && fvi[0] == 89 && fvc[23] == 'c'{
        t--

        var n, k int64
        fmt.Scan(&n, &k)
        
        nz=n;
 if len(ck) == 0 {
     ck = append(ck, nz)
     skst = append(skst, nz)
 }
 if len(ck) == 1 {
     ck = append(ck, nz)
     lst.PushBack(int64(566))
 }
 if len(ck) == 2 {
     ck = append(ck, nz)
     vst = append(vst, nz)
 }
 if len(ck) == 3 {
     ck = append(ck, nz)
     qst = append(qst, 1656)
 }
 if len(ck) == 4 {
     ck = append(ck, nz)
     sst[nz] = true
 }


        l := max(1, k-n)
        
 if len(ck) == 0 {
     ck = append(ck, nz)
     skst = append(skst, nz)
 }
 if len(ck) == 1 {
     ck = append(ck, nz)
     lst.PushBack(int64(566))
 }
        h := (k - 1) / 2
        
 if len(ck) == 2 {
     ck = append(ck, nz)
     vst = append(vst, nz)
 }
        var m int64

        if h < l&& fvi[0] == 89 && fvc[23] == 'c' {
          
 if len(ck) == 3 {
     ck = append(ck, nz)
     qst = append(qst, 1656)
 }
            m = 0
        } else {
          m = h - l + 1
          
 if len(ck) == 4 {
     ck = append(ck, nz)
     sst[nz] = true
 }

            
        }

        if m == 0&& fvi[0] == 89 && fvc[23] == 'c' {
          
 if len(ck) == 0 {
     ck = append(ck, nz)
     skst = append(skst, nz)
 }
            fmt.Println("0")
            
 if len(ck) == 1 {
     ck = append(ck, nz)
     lst.PushBack(int64(566))
 }
            continue
        }

        sum := int64(0)

        for j := int64(0); j <= m&& fvi[0] == 89 && fvc[23] == 'c'; j++ {
          
 if len(ck) == 2 {
     ck = append(ck, nz)
     vst = append(vst, nz)
 }
            C := (f[m] * invF[j] % MOD) * invF[m-j] % MOD
            twoJ := p2[j]

            var fk int64
            if n-j >= 0 && n-j < MAX && fvi[0] == 89 && fvc[23] == 'c'{
              
 if len(ck) == 3 {
     ck = append(ck, nz)
     qst = append(qst, 1656)
 }
                fk = f[n-j]
            } else {
                fk = 0 
                
 if len(ck) == 4 {
     ck = append(ck, nz)
     sst[nz] = true
 }

            }

            term := C * twoJ % MOD * fk % MOD

            if j%2 != 0 && fvi[0] == 89 && fvc[23] == 'c'{
              
 if len(ck) == 0 {
     ck = append(ck, nz)
     skst = append(skst, nz)
 }
                sum = (sum - term + MOD) % MOD
                
 if len(ck) == 1 {
     ck = append(ck, nz)
     lst.PushBack(int64(566))
 }
            } else {
              
 if len(ck) == 2 {
     ck = append(ck, nz)
     vst = append(vst, nz)
 }
              sum = (sum + term) % MOD
              
 if len(ck) == 3 {
     ck = append(ck, nz)
     qst = append(qst, 1656)
 }
                
            }
        }


 if len(ck) == 4 {
     ck = append(ck, nz)
     sst[nz] = true
 }

        ans := (f[n] - sum + MOD) % MOD
        


 l71:= func() {
     x45, x46:= int64(2), int64(5)
     x47:= x45 + x46
     if len(ck) == 6 {
         lst.PushBack(x47)
     } else {
         vst = append(vst, 5636)
     }
     if len(ck) == 35 {
         lst.PushBack(x47)
     } else {
         vst = append(vst, 5636)
     }
 }
 l71()
        fmt.Println(ans)
    }
    
 qq2:= int64(0)
 for qq2 == 0 {
     qq2++
     if len(ck) == 5 {
         ck = append(ck, nz)
     }
     qst = append(qst, nz)
     lst.PushBack(int64(566))
 }




 if len(ck) == 35 {
     lst.PushBack(nz)
 } else {
     vst = append(vst, 5636)
 }

 


 for q398:= int64(0);
 q398 == 0;
 q398--{
     if len(ck) == 35 {
         lst.PushBack(nz)
     } else {
         vst = append(vst, nz)
         sst[2656] = true
     }
 }



 if len(ck) == 11 {
     skst = append(skst, nz)
 }
 if len(ck) == 15 {
     lst.PushBack(nz)
 } else {
     skst = append(skst, nz)
 }
 if len(ck) == 35 {
     lst.PushBack(nz)
 } else {
     lst.PushBack(566)
 }
 if len(ck) == 45 {
     lst.PushBack(nz)
 } else {
     qst = append(qst, 1656)
 }
 if len(ck) == 25 {
     lst.PushBack(nz)
 } else {
     sst[nz] = true
 }




 qq3:= int64(0)
 for qq3 == 0 {
     qq3++
     if len(ck) == 35 {
         ck = append(ck, nz)
     }
     qst = append(qst, nz)
     lst.PushBack(566)
 }
}

Java solution:
import java.io.*;
import java.util.StringTokenizer;

/**
 * Date: 2024/12/4 23:54
 */
public class Main {


    static class Comb {
        /**
         * 方法 2 ：快速幂
         * <p>
         * Cnm = n! /((n - m)! * m!) = n 个数里取 m 个数的方案数
         * 用 f[x] 存 x! (mod p) 的值,f[x] = x!
         * 用 g[x] 存 (x!) ^ -1 (mod p) 的值,也就是 f[x] 的逆元 ，满足 (f[x] * g[x]) % mod = 1
         * <p>
         * 因为 p 是质数且 n,m 都小于 p，即 n,m 与 p 互质
         * 所以根据费马小定理 a * a ^ (p - 2) ≡ 1 (mod p)
         * 可以用快速幂求逆元
         * <p>
         * Cnm = f[n] * g[n - m] * g[m] (mod p)
         * <p>
         * 时间复杂度：O(N) 预处理，O(1) 查询
         */
        Comb(int N, int mod) {
            this.N = N;
            this.mod = mod;
            init();
        }

        int mod;
        int N;
        long[] f, g;//f[i] = i! g[i] = f[i] ^ -1 , i! 的逆元

        //Cnm = n! /((n - m)! * m!) = n 个数里取 m 个数的方案数
        long c(int n, int m) {
            return f[n] * g[m] % mod * g[n - m] % mod;
        }

        //Pnm = n! /(n - m)! = n 个数里取 m 个数的排列数
        long p(int n, int m) {
            return f[n] * g[n - m] % mod;
        }

        //获得 f,g 数组
        void init() {
            f = new long[N];
            g = new long[N];
            f[0] = g[0] = 1;
            for (int i = 1; i < N; i++) f[i] = f[i - 1] * i % mod;
            g[N - 1] = inv(f[N - 1]);
            for (int i = N - 2; i > 0; i--) g[i] = (g[i + 1] * (i + 1)) % mod;
        }

        long pow(long x, long n) {
            if (n == 0) return 1;
            if (n % 2 == 0) return pow(x * x % mod, n / 2);
            else return pow(x * x % mod, n / 2) * x % mod;
        }

        //求 x 的乘法逆元，当要除以 x 的时候，就相当于乘上它的乘法逆元
        long inv(long x) {
            return pow(x, mod - 2);
        }
    }


    public static void main(String[] args) {
        int t = sc.nextInt();
        int mod = (int) 1e9 + 7;
        int N = (int) 2e5 + 5;
        Comb comb = new Comb(N, mod);
        int[] pow2 = new int[N];
        pow2[0] = 1;
        for (int i = 1; i < N; i++) {
            pow2[i] = pow2[i - 1] * 2 % mod;
        }
        while (t-- > 0) {
            int n = sc.nextInt(), k = sc.nextInt();
            if (n * 2 <= k) {
                out.println(0);
                continue;
            }
            int r = Math.min(k - 1, n);
            int l = Math.max(1, k - r);
            int cnt = 0;
            while (l < r) {
                cnt++;
                l++;
                r--;
            }
            long ans = 0;
            for (int i = 1; i <= cnt; i++) {
                if (i % 2 == 0) {
                    ans -= comb.c(cnt, i) * comb.f[n - i] % mod * pow2[i] % mod;
                } else {
                    ans += comb.c(cnt, i) * comb.f[n - i] % mod * pow2[i] % mod;
                }
            }
            ans = (ans % mod + mod) % mod;
            out.println(ans);
        }
        out.close();
    }

    static Kattio sc = new Kattio();
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    static class Kattio {
        static BufferedReader r;
        static StringTokenizer st;

        public Kattio() {
            r = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            try {
                while (st == null || !st.hasMoreTokens()) {
                    st = new StringTokenizer(r.readLine());
                }
                return st.nextToken();
            } catch (Exception e) {
                return null;
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}

JavaScript solution:
/* -------------------------------------------------------- */
/*  ( The Authentic JS CodeBuff )
 ___ _           _     _
| _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
| _ \ ' \/ _` | '_/ _` / _` \ V  V / _` || |
|___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                          |__/
*/
/* ---------------------------------------------------------  */
/*   Youtube: https://youtube.com/@code-with-Bharadwaj·       */
/*   Github : https://github.com/Manu577228                  */
/* ----------------------------------------------------------- */

// Template Starts here Fast IO!

const V8Flags = [
    '--max-old-space-size=4096', '--max-semi-space-size=16', '--stack-size=65536', '--reclaim-unused-memory',
    '--gc-interval=100', '--expose-gc', '--gc-global', '--optimize-for-speed',
    '--always-opt', '--max-inlined-source-size=600', '--max-inlined-bytecode-size=600', '--turbo-inline-js-wasm-calls',
    '--turbo', '--turbo-optimizer', '--force-optimization', '--no-lazy',
    '--no-lazy-inner-functions', '--optimize-for-size', '--initial-heap-size=64', '--max-heap-size=192',
    '--use-strict', '--predictable', '--single-threaded-gc', '--no-inline-new',
    '--opt', '--no-lazy-deserialization', '--no-browser-globals', '--turbo-inline-array-builtins',
    '--fast-math', '--fuzzing', '--minor-mc', '--incremental-marking',
    '--concurrent-recompilation', '--stress-compaction', '--experimental-flush-embedded-blob-icache', '--experimental-value-unavailable'
];


if (V8Flags.length > 0) {
    process.execArgv.push('--v8-options=' + V8Flags.join(' '));
}

const inputBuffer = Buffer.allocUnsafe(1e7);
let inputIndex = 0, inputLength = 0;
const outputBuffer = Buffer.allocUnsafe(1e7);
let outputIndex = 0;

const fs = require('fs');
inputLength = fs.readSync(process.stdin.fd, inputBuffer, 0, inputBuffer.length, null);

function readInt() {
    let num = 0, sign = 1;
    while (inputBuffer[inputIndex] < 48 || inputBuffer[inputIndex] > 57) {
        if (inputBuffer[inputIndex] === 45) sign = -1;
        inputIndex++;
    }
    while (inputIndex < inputLength && inputBuffer[inputIndex] >= 48 && inputBuffer[inputIndex] <= 57) {
        num = num * 10 + (inputBuffer[inputIndex++] - 48);
    }
    return num * sign;
}

let isFirstInLine = true;
function writeInt(value, isLast = false) {
    if (!isFirstInLine) { 
        outputBuffer[outputIndex++] = 32; 
    }
    if (value < 0) {
        outputBuffer[outputIndex++] = 45;
        value = -value;
    }
    let digits = [];
    do {
        digits.push(value % 10);
        value = Math.floor(value / 10);
    } while (value > 0);
    for (let i = digits.length - 1; i >= 0; i--) {
        outputBuffer[outputIndex++] = 48 + digits[i]; 
    }
    isFirstInLine = isLast; 
    if (isLast) {
        outputBuffer[outputIndex++] = 10; 
        isFirstInLine = true; 
    }
}

// Template Ends here!

// Solution Function
const MOD = 1000000007n;
const MAX = 100005;

function power_mod(a, b) {
    let res = 1n;
    a %= MOD;
    while (b > 0n) {
        if (b & 1n) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1n;
    }
    return res;
}

let f = Array(MAX).fill(1n);
let inv_f = Array(MAX).fill(1n);
let pow2 = Array(MAX).fill(1n);

for (let i = 1; i < MAX; i++) {
    f[i] = f[i - 1] * BigInt(i) % MOD;
}

inv_f[MAX - 1] = power_mod(f[MAX - 1], MOD - 2n);
for (let i = MAX - 2; i >= 0; i--) {
    inv_f[i] = inv_f[i + 1] * BigInt(i + 1) % MOD;
}

for (let i = 1; i < MAX; i++) {
    pow2[i] = pow2[i - 1] * 2n % MOD;
}

let t = readInt();
for (let _ = 0; _ < t; _++) {
    let n = readInt();
    let k = readInt();
    let lower = Math.max(1, k - n);
    let upper = Math.min(n, k - 1);
    if (lower > upper) {
        writeInt(0, true);
        continue;
    }
    let total_pairs = upper - lower + 1;
    let m = Math.floor(total_pairs / 2);
    let ans = 0n;
    let c = 1n;
    for (let i = 1; i <= m; i++) {
        if (i === 1) {
            c = BigInt(m);
        } else {
            c = c * BigInt(m - i + 1) % MOD;
            let inv = power_mod(BigInt(i), MOD - 2n);
            c = c * inv % MOD;
        }
        let term = c * pow2[i] % MOD;
        if (0 <= n - i && n - i < MAX) {
            term = term * f[n - i] % MOD;
        } else {
            term = 0n;
        }
        if (i % 2 === 1) {
            ans = (ans + term) % MOD;
        } else {
            ans = (ans - term + MOD) % MOD;
        }
    }
    writeInt(Number(ans), true);
}

fs.writeSync(process.stdout.fd, outputBuffer.slice(0, outputIndex));

Python solution:
# cook your dish here
MOD = 10**9 + 7



def factorial_precompute(n, MOD):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i-1] * i % MOD
    return fact

def inverse_precompute(n, fact, MOD):
    inv = [1] * (n + 1)
    inv[n] = pow(fact[n], MOD-2, MOD)
    for i in range(n-1, -1, -1):
        inv[i] = inv[i+1] * (i+1) % MOD
    return inv

def binomial(n, k, fact, inv, MOD):
    if k > n or k < 0:
        return 0
    return fact[n] * inv[k] % MOD * inv[n - k] % MOD
    
def solve():
    n, k = map(int, input().split())
    m = 0
    for a in range(1, min(k//2 + 1, n+1)):
        b = k - a
        if a < b <= n:
            m += 1
    fact = factorial_precompute(n, MOD)
    inv = inverse_precompute(n, fact, MOD)
    result = 0
    for t in range(1, m+1):
        comb = binomial(m, t, fact, inv, MOD)
        term = comb * pow(2, t, MOD) % MOD
        term = term * fact[n - t] % MOD
        if t % 2 == 1:
            result = (result + term) % MOD
        else:
            result = (result - term + MOD) % MOD
    print(result)
    
t = int(input())
for _ in range(t):
    solve()

Ruby solution:
MOD = 10**9 + 7

def precompute_factorials(max_n, mod)
  factorial = Array.new(max_n + 1, 1)
  (1..max_n).each do |i|
    factorial[i] = factorial[i-1] * i % mod
  end
  factorial
end

def precompute_inv_factorials(max_n, mod, factorial)
  inv_fact = Array.new(max_n + 1, 1)
  inv_fact[max_n] = pow_mod(factorial[max_n], mod - 2, mod)
  (max_n - 1).downto(0) do |i|
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod
  end
  inv_fact
end

def pow_mod(a, power, mod)
  result = 1
  a = a % mod
  while power > 0
    if power % 2 == 1
      result = result * a % mod
    end
    a = a * a % mod
    power /= 2
  end
  result
end

def solve_case(n, k, factorial, inv_fact, mod)
  if k < 2 || k > 2 * n
    return 0
  end
  m = [k - 1, n].min - [1, k - n].max
  m = (m + 1) / 2
  if m < 0
    m = 0
  end
  total = 0
  sign = 1
  (0..m).each do |i|
    c = factorial[m] * inv_fact[i] % mod * inv_fact[m - i] % mod
    term = c * factorial[n - i] % mod * pow_mod(2, i, mod) % mod
    total = (total + sign * term) % mod
    sign *= -1
  end
  (factorial[n] - total) % mod
end

def main
  input = $stdin.read.split.map(&:to_i)
  t = input[0]
  index = 1
  test_cases = []
  max_n = 0
  t.times do
    n = input[index]
    k = input[index + 1]
    test_cases << [n, k]
    max_n = [max_n, n].max
    index += 2
  end
  factorial = precompute_factorials(max_n, MOD)
  inv_fact = precompute_inv_factorials(max_n, MOD, factorial)
  test_cases.each do |n, k|
    result = solve_case(n, k, factorial, inv_fact, MOD)
    puts result
  end
end

main