#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define UINT unsigned int
#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using namespace __gnu_pbds;

using pii = pair<int, int>;
using indexed_set = tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>;

const clock_t START_T = clock();
const int MOD = 1e6+3;

double time_running(){
    return (double)(clock() - START_T) / CLOCKS_PER_SEC;
}

int add_mod(int a, int b){
    a += b;
    if (a < 0) a += MOD;
    if (a >= MOD) a -= MOD;
    return a;
}

inline int mul_mod(int a, int b){
    return (LL)a * b % MOD;
}

int exp_by_sqr(int a, int n){
    if (n == 0)
        return 1;
    return (n & 1) ? mul_mod(a, exp_by_sqr(a, n-1)) : exp_by_sqr(mul_mod(a, a), n >> 1);
}

int main(){
    ifstream cin("inversions.in");
    ofstream cout("inversions.out");
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    int n;
    LL k, cnt = 0;
    cin >> n >> k;
    V<int> a(n);
    FORI(i,0,n){
        cin >> a[i];
    }
    int l = 0, r = 0, ans = exp_by_sqr(2, n-1);
    indexed_set pref;
    while(l < n){
        while(cnt <= k && r+1 < n){
            pref.insert({a[r], r});
            cnt += SZ(pref) - pref.order_of_key({a[++r], n});
        }
        if (cnt > k){
//            cerr << l << ' ' << r << endl;
            ans = add_mod(ans, -exp_by_sqr(2, n - (r - l + 1)));
        }
        pref.erase({a[l], l});
        cnt -= pref.order_of_key({a[l], -1});
        l++;
    }
    cout << ans;

//    cerr << time_running() << endl;
    return 0;
}