#include <bits/stdc++.h>    
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//using namespace __gnu_pbds; 
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb  push_back
#define show(x) cout<<(#x)<<" : "<<x<<endl;
#define ll  long long
#define ld  long double
#define fill(a,val) memset(a,val,sizeof(a))
#define mp  make_pair
#define ff  first
#define ss  second
#define pii pair<ll,ll>
#define sq(x) ((x)*(x))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define endl "\n"
#define int long long 
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
const ll MOD     = 1000*1000*1000+7;
const ll INF     = 1ll*1000*1000*1000*1000*1000*1000 + 7;
const ll MOD2    = 998244353;
const ll N       = 1000 * 100 + 10;
const ll N2      = 70;
const ld PI  = 3.141592653589793;
//template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);} 
ll power(ll x,ll y,ll p = LLONG_MAX ){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
ll lcm(ll a , ll b){return (a*b)/gcd(a,b);}
int getSum(int BITree[], int index) 
{ 
    int sum = 0; // Initialize result 
  
    // index in BITree[] is 1 more than the index in arr[] 
    index = index + 1; 
  
    // Traverse ancestors of BITree[index] 
    while (index>0) 
    { 
        // Add current element of BITree to sum 
        sum += BITree[index]; 
        sum%=MOD2;
  
        // Move index to parent node in getSum View 
        index -= index & (-index); 
    } 
    return sum; 
} 
  
// Updates a node in Binary Index Tree (BITree) at given 
// index in BITree.  The given value 'val' is added to 
// BITree[i] and all of its ancestors in tree. 
void updateBIT(int BITree[], int n, int index, int val) 
{ 
    // index in BITree[] is 1 more than the index in arr[] 
    index = index + 1; 
  
    // Traverse all ancestors and add 'val' 
    while (index <= n) 
    { 
        // Add 'val' to current node of BI Tree 
        BITree[index] += val; 
        BITree[index]%=MOD2;
        // Update index to that of parent in update View 
        index += index & (-index); 
    } 
} 
  
// Returns the sum of array from [0, x] 
int sum(int x, int BITTree1[], int BITTree2[]) 
{ 
    return ((getSum(BITTree1, x) * x) - getSum(BITTree2, x) + MOD2)%MOD2; 
} 
  
  
void updateRange(int BITTree1[], int BITTree2[], int n, 
                 int val, int l, int r) 
{ 
    // Update Both the Binary Index Trees 
    // As discussed in the article 
  
    // Update BIT1 
    updateBIT(BITTree1,n,l,val); 
    updateBIT(BITTree1,n,r+1,-val); 
  
    // Update BIT2 
    updateBIT(BITTree2,n,l,val*(l-1)); 
    updateBIT(BITTree2,n,r+1,-val*r); 
} 
  
int rangeSum(int l, int r, int BITTree1[], int BITTree2[]) 
{ 
    // Find sum from [0,r] then subtract sum 
    // from [0,l-1] in order to find sum from 
    // [l,r] 
    return (sum(r, BITTree1, BITTree2) - 
           sum(l-1, BITTree1, BITTree2) + MOD2 )%MOD2 ; 
} 
  
  
int *constructBITree(int n) 
{ 
    // Create and initialize BITree[] as 0 
    int *BITree = new int[n+1]; 
    for (int i=1; i<=n; i++) 
        BITree[i] = 0; 
  
    return BITree; 
}
signed main()
{
    fastio();
    //cout<<fixed<<setprecision(20);
    //CHECK for LONG LONG and LONG DOUBLE
    //*comment for all except cc/cf    
    #ifndef ONLINE_JUDGE    
           freopen("input.txt","r",stdin);
           freopen("output.txt","w",stdout);
    #endif//*/ 
    int n,k;
    cin>>n>>k;
    std::vector<pii> v(n);
    for (int i = 0; i < n; ++i)
        cin>>v[i].ff>>v[i].ss;

    int *BITTree1, *BITTree2; 
    BITTree2 = constructBITree(n); 
    BITTree1 = constructBITree(n);
    updateRange(BITTree1,BITTree2,n,1,0,0);
    for (int i = 0; i < n; ++i)
    {
        int val = rangeSum(i,i,BITTree1,BITTree2);
        for (int j = 0; j < k; ++j)
        {
            int l = i + v[j].ff;
            int r = i + v[j].ss;
            if(i>=n) continue;
            r = min(r,n-1);
            updateRange(BITTree1,BITTree2,n,val,l,r);
        }
    }
    cout<<rangeSum(n-1,n-1,BITTree1,BITTree2);
    printclock;
    return 0;
}

Measured memory_bytes: 9512