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