zrq’s blogPE 405

#include <cstdio>
using namespace std;
typedef long long LL;
const LL M = 410338673;
const LL phiM = 386201104;
LL (LL a,LL b,LL c)
{
	LL ret = 1;
	for (;b;b >>= 1,a = a * a % c)
		if (b & 1) ret = ret * a % c;
	return ret;
}
int main()
{
	LL n = ksm(10,(LL)1e18,phiM);
	LL ans = -1ll - 20ll * ksm(2,n,M) + 6ll * ksm(4,n,M);
	ans = ans * ksm(15,phiM - 1,M) % M;
	ans = (ans % M + M + 1) % M;
	cout << ans << endl;
}