Đây là một bài quy hoạch động đơn giản.

Ta có thể hình dung như sau:

Gọi ~F[i]~ là số cách thiết lập từ vị trí ~1~ đến ~i~. Ta có:

• Nếu ta cho bit ~i~ này là 0 thì kết quả sẽ là ~F[i - 1]~ và gắn thêm số 0 vào.
• Nếu ta cho bit ~i~ này là 1 thì ta không được sử dụng kết quả của ~F[i - 1]~ mà phải là ~F[i - 2]~ và gắn cả 01 vào.

Vậy công thức truy hồi của chúng ta sẽ là:

$$ F[i] = F[i - 1] + F[i - 2] $$

Nhìn quen không? Đúng vậy, nó là công thức truy hồi của dãy Fibonacci. Nhưng ta phải xây dựng base case trước.

• Với độ dài là 0, ta chỉ có 1 cách là không làm gì hết: ~F[0] = 1~.
• Với độ dài là 0, ta có 2 cách là Tắt hoặc Bật: ~F[1] = 2~.

Khi có thêm ~p~ vào. Việc ta cần làm là dùng quy tắc nhân bên trái vị trí ~p~ và bên phải vị trí ~p~. Ta biết rằng là khi vị trí ~p~ là 1 thì ~p - 1~ và ~p + 1~ phải là 0. Nên ta có công thức sau:

$$ Result = F[p - 2] \times F[N - (p + 2) + 1] $$

Hay rút gọn thành:

$$ Result = F[p - 2] \times F[N - p - 1] $$

Phần còn lại là xử với khả năng các trường hợp biên.

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

const int MOD = 1e9 + 7;
const int MAXN = 200005;

long long f[MAXN];

void prepare() {
    f[1] = 1;
    f[2] = 1;
    for (int i = 3; i < MAXN; i++) {
        f[i] = (f[i - 1] + f[i - 2]) % MOD;
    }
}

void solve() {
    int n, p;
    cin >> n >> p;
    long long ans = (f[p] * f[n - p + 1]) % MOD;
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    prepare();

    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}