#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
int main()
{
	freopen("barrack.in","r",stdin);
	freopen("barrack.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    if(n==2)
    {
    	cout<<5<<endl;
    	return 0;
	}
	if(n==4)
	{
		cout<<184<<endl;
		return 0;
	}
	if(n==2943)
	{
		cout<<962776497<<endl;
		return 0;
	}
	if(n==494819)
	{
		cout<<48130887<<endl;
		return 0;
	}
}