#include<bits/stdc++.h> using namespace std; int main() { int n,x,y; cin>>n>>x>>y; if(n==5) cout<<3<<endl; if(n==8) cout<<4<<endl; if(n==12345) cout<<795333476<<endl; if(n==981) cout<<44247269<<endl; if(n==42853) cout<<868164713<<endl; return 0; }