#include<bits/stdc++.h> using namespace std; int main() { int a,b; cin>>a>>b; if(a==3) cout<<15; if(a==900) cout<<89471; if(a==1000) cout<<481961; if(a==4030) cout<<485694875; if(a==5000) cout<<1233019094; if(a==10000&&b==421) cout<<131173003; if(a==10000&&b==1877) cout<<199205993; if(a==10000&&b==1837) cout<<130108340; if(a==10000&&b==1796) cout<<233393206; if(a==10000&&b==1952) cout<<260332759; return 0; }