#include #include #include #include #include #include #include #include #include #include #include #include #define vll vector #define vvvl vector #define vvl vector> #define VV(a, b, c, d) vector>(a, vector(b, c)) #define VVV(a, b, c, d) vector(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c> n; init(); ll x = (n-2)%P; ll y = (n-3)%P; ll ans = (inv[2]*((x*y)%P))%P; //std::cout << ans << '\n'; //全て6回カウント、ただし2個被りは3回、3個被りは1回カウント if((n-4)%3==0) ans = (ans + 2)%P; //std::cout << ans << '\n'; ans = (ans + (3*(1+(((n-4)/2)%P)%P))%P )%P; ans = (ans * inv[6])%P; std::cout << ans << '\n'; return 0; }