Page Contents

Excellent Arrays Codeforces Solution

Let’s call an integer array a1,a2,…,ana1,a2,…,an good if ai≠iai≠i for each ii. Let F(a)F(a) be the number of pairs (i,j)(i,j) (1≤i<j≤n1≤i<j≤n) such that ai+aj=i+jai+aj=i+j.

Let’s say that an array a1,a2,…,ana1,a2,…,an is excellent if:

aa is good;
l≤ai≤rl≤ai≤r for each ii;
F(a)F(a) is the maximum possible among all good arrays of size nn.

Given nn, ll and rr, calculate the number of excellent arrays modulo 109+7109+7.Input

The first line contains a single integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

The first and only line of each test case contains three integers nn, ll, and rr (2≤n≤2⋅1052≤n≤2⋅105; −109≤l≤1−109≤l≤1; n≤r≤109n≤r≤109).

It’s guaranteed that the sum of nn doesn’t exceed 2⋅1052⋅105.Output

For each test case, print the number of excellent arrays modulo 109+7109+7.

Example

input

output

Note

In the first test case, it can be proven that the maximum F(a)F(a) among all good arrays aa is equal to 22. The excellent arrays are:

[2,1,2][2,1,2];
[0,3,2][0,3,2];
[2,3,2][2,3,2];
[3,0,1][3,0,1].

Solution

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

#define debug(...) do {\
	fprintf(stderr, "%s - %d : (%s) = ", __PRETTY_FUNCTION__, __LINE__, #__VA_ARGS__);\
    _DO(__VA_ARGS__);\
}while(0) 
template<typename I> void _DO(I&&x) {cerr << x << '\n';}
template<typename I, typename ...T> void _DO(I&&x,T&&...tail) {cerr << x << ", "; _DO(tail...);}
#define IOS
#else
#define debug(...)
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
#endif
#define FOR(i, n) for(int i = 0; i < n; i++)
#define FOR1(i, n) for(int i = 1; i <= n; i++)
#define pb push_back
#define mp make_pair
#define rsz resize
#define X first
#define Y second
#define SZ(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort(ALL(x))
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
const int NF = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9 + 7;
const ld PI = 3.14159265358979323846264338327950288;

ll fact[200005], invfact[200005];
ll mypow(ll a, ll x){
    if (x == 0) return 1;
    if (x == 1) return a;
    ll tmp = mypow(a, x >> 1);
    tmp = tmp * tmp % MOD;
    if (x & 1) tmp *= a;
    return tmp % MOD;
}
ll inv(ll a){
    return mypow(a, MOD - 2);
}
ll C(ll n, ll k){
    return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
}
ll n, l, r;
ll sub(ll p, ll m, ll x){
    if (p < l + x - 1) return 0;
    if (m < n - (r - x + 1) + 1) return 0;
    p -= max(l + x - 1LL, 0LL);
    m -= max((ll)(n - (r - x + 1) + 1), 0LL);
    return C(m + p, p);
}
int main() {
    IOS;
    int t;
    cin >> t;
    fact[0] = 1;
    invfact[0] = 1;
    for (ll i = 1; i < 200005; i++){
        fact[i] = fact[i - 1] * i % MOD;
        invfact[i] = inv(fact[i]);
    }
    while (t--){
        cin >> n >> l >> r;
        ll ans = min(r - n, 1LL - l) * ((n & 1) ? C(n, n / 2) + C(n, n / 2 + 1) : C(n, n / 2));
        ans %= MOD;

        for (ll x = min(r - n, 1LL - l) + 1; x <= min(r - 1LL, n - l); x++){
            if (l + x - 1 >= r - x + 1) break;

            if (n & 1){
                ans += sub(n / 2, n / 2 + 1, x);
                ans %= MOD;
                ans += sub(n / 2 + 1, n / 2, x);
                ans %= MOD;
            }
            else {
                ans += sub(n / 2, n / 2, x);
                ans %= MOD;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

Educational Codeforces Round 111 (Rated for Div. 2)

Excellent Arrays Codeforces Solution
Stringforces Codeforces Solution
Jumping Around Codeforces Solution
Manhattan Subarrays Codeforces Solution
Maximum Cost Deletion Codeforces Solution
Find The Array Codeforces Solution

Excellent Arrays Codeforces Solution

Solution

Educational Codeforces Round 111 (Rated for Div. 2)

Leave a Comment Cancel reply