結果
| 問題 | No.1348 Split Tile |
| ユーザー |
 PCTprobability
|
| 提出日時 | 2021-01-13 22:54:00 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 7 ms / 2,000 ms |
| コード長 | 34,801 bytes |
| コンパイル時間 | 3,534 ms |
| コンパイル使用メモリ | 226,692 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-22 19:31:55 |
| 合計ジャッジ時間 | 4,740 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,248 KB |
| testcase_02 | AC | 2 ms
5,248 KB |
| testcase_03 | AC | 7 ms
5,248 KB |
| testcase_04 | AC | 5 ms
5,248 KB |
| testcase_05 | AC | 2 ms
5,248 KB |
| testcase_06 | AC | 3 ms
5,248 KB |
| testcase_07 | AC | 6 ms
5,248 KB |
| testcase_08 | AC | 5 ms
5,248 KB |
| testcase_09 | AC | 5 ms
5,248 KB |
| testcase_10 | AC | 6 ms
5,248 KB |
| testcase_11 | AC | 3 ms
5,248 KB |
| testcase_12 | AC | 4 ms
5,248 KB |
| testcase_13 | AC | 5 ms
5,248 KB |
| testcase_14 | AC | 4 ms
5,248 KB |
| testcase_15 | AC | 6 ms
5,248 KB |
| testcase_16 | AC | 4 ms
5,248 KB |
| testcase_17 | AC | 3 ms
5,248 KB |
| testcase_18 | AC | 5 ms
5,248 KB |
| testcase_19 | AC | 4 ms
5,248 KB |
| testcase_20 | AC | 4 ms
5,248 KB |
| testcase_21 | AC | 4 ms
5,248 KB |
| testcase_22 | AC | 6 ms
5,248 KB |
| testcase_23 | AC | 6 ms
5,248 KB |
| testcase_24 | AC | 7 ms
5,248 KB |
| testcase_25 | AC | 7 ms
5,248 KB |
| testcase_26 | AC | 7 ms
5,248 KB |
| testcase_27 | AC | 7 ms
5,248 KB |
ソースコード
////////////////////////////////////////////////////////////////////////////////
// Give me AC!!! //
////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using ll = long long;
using ld = long double;
using graph = vector<vector<int>>;
#define NDEBUG
using int64 = long long;
const int64 infll = (1LL << 62) - 1;
#define all(s) (s).begin(),(s).end()
#define sz(x) (int) (x).size()
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
#define PQ priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>>
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define S second //pairの二つ目の要素
#define coutY cout<<"YES"<<endl
#define couty cout<<"Yes"<<endl
#define coutN cout<<"NO"<<endl
#define coutn cout<<"No"<<endl
#define coutdouble(a,b) cout << fixed << setprecision(a) << double(b) ;
#define vi(a,b) vector<int> a(b)
#define vl(a,b) vector<ll> a(b)
#define vs(a,b) vector<string> a(b)
#define vll(a,b,c) vector<vector<ll>> a(b, vector<ll>(c));
#define intque(a) queue<int> a;
#define llque(a) queue<ll> a;
#define intque2(a) priority_queue<int, vector<int>, greater<int>> a;
#define llque2(a) priority_queue<ll, vector<ll>, greater<ll>> a;
#define pushback(a,b) a.push_back(b)
#define mapii(M1) map<int, int> M1;
#define cou(v,x) count(v.begin(), v.end(), x)
#define mapll(M1) map<ll,ll> M1;
#define mapls(M1) map<ll, string> M1;
#define mapsl(M1) map<string, ll> M1;
#define twolook(a,l,r,x) lower_bound(a+l, a+r, x) - a
#define sor(a) sort(a.begin(), a.end())
#define rever(a) reverse(a.begin(),a.end())
#define rep(i,a) for(ll i=0;i<a;i++)
#define vcin(n) for(ll i=0;i<ll(n.size());i++) cin>>n[i]
#define vcout(n) for(ll i=0;i<ll(n.size());i++) cout<<n[i]
#define vcin2(n) rep(i,ll(n.size())) rep(j,ll(n.at(0).size())) cin>>n[i][j]
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
const ll mod = 998244353;
const ll MOD = 998244353;
//const ll MOD=1000000007;
//const ll mod=1000000007;
constexpr ll MAX = 500000;
//const ll _max = 9223372036854775807;
const ll _max = 1223372036854775807;
const ll inf = 2000000000000000000ll;
static const long double pi = 3.141592653589793;
const int MAX_COL=350;
const int MAX_ROW=350;
ll fac[MAX],finv[MAX],inv[MAX];
typedef int FLOW; // フローを表す型、今回は int 型
const int MAX_V = 6000; // グラフの最大ノード数
const FLOW INF = 100000000;
// テーブルを作る前処理
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
// 二項係数計算
long long COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
ll HOM(ll n,ll k){
if(n+k-1>=n-1&&n-1>=0){
return COM(n+k-1,n-1);
}
else{
return 0;
}
}
ll modPow(long long a, long long n, long long p) {
if (a == 0 && n == 0) return 1;
if (n == 0) return 1; // 0乗にも対応する場合
if (n == 1) return a % p;
if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
long long t = modPow(a, n / 2, p);
return (t * t) % p;
}
ll clocks(ll a,ll b,ll c){
return a*3600+b*60+c;
}
ll divup(ll b,ll d){
if(b%d==0){
return b/d;
}
else{
return b/d+1;
}
}
ll zero(ll a){
return max(ll(0),a);
}
//aはbの何乗以下かを満たす数の内最大の物,(a,10)はaの桁数
ll expless(ll a,ll b){
ll k=0;
ll o=1;
while(a>=o){
k++;
o=o*b;
}
return k;
}
//aをb進法で表す
//b進法のaを10進法に直す
ll tenbase(ll a,ll b){
ll c=expless(a,10);
ll ans=0;
ll k=1;
for(int i=0;i<c;i++){
ans+=(a%10)*k;
k=k*b;
a=a/10;
}
return ans;
}
vector<pair<long long, long long> > prime_factorize(long long N) {
vector<pair<long long, long long> > res;
for (long long a = 2; a * a <= N; ++a) {
if (N % a != 0) continue;
long long ex = 0; // 指数
// 割れる限り割り続ける
while (N % a == 0) {
++ex;
N /= a;
}
// その結果を push
res.push_back({a, ex});
}
// 最後に残った数について
if (N != 1) res.push_back({N, 1});
return res;
}
template <class T, class U>
void chmin(T& t, const U& u) {
if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
if (t < u) t = u;
}
//aがbで何回割り切るか
ll exp(ll a,ll b){
ll ans=0;
while(a%b==0){
a=a/b;
ans++;
}
return ans;
}
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int X[6]={1,1,0,-1,-1,0};
const int Y[6]={0,1,1,0,-1,-1};
template<typename T>
vector<T> smallest_prime_factors(T n) {
vector<T> spf(n + 1);
for (int i = 0; i <= n; i++) spf[i] = i;
for (T i = 2; i * i <= n; i++) {
// 素数だったら
if (spf[i] == i) {
for (T j = i * i; j <= n; j += i) {
// iを持つ整数かつまだ素数が決まっていないなら
if (spf[j] == j) {
spf[j] = i;
}
}
}
}
return spf;
}
vector<pair<ll,ll>> factolization(ll x, vector<ll> &spf) {
vector<pair<ll,ll>> ret;
ll p;
ll z;
while (x != 1) {
p=(spf[x]);
z=0;
while(x%p==0){
z++;
x /= p;
}
ret.push_back({p, z});
}
return ret;
}
vector<bool> is;
vector<long long int> prime_(ll n){
is.resize(n+1, true);
is[0] = false;
is[1] = false;
vector<long long int> primes;
for (int i=2; i<=n; i++) {
if (is[i] == true){
primes.push_back(i);
for (int j=i*2; j<=n; j+=i){
is[j] = false;
}
}
}
return primes;
}
ll so(ll a){
ll ans=0;
if(a==0){
return 0;
}
while(a%2==0){
a/=2;
ans++;
}
return ans;
}
ll binary(ll bina){
ll ans = 0;
for (ll i = 0; bina>0 ; i++)
{
ans = ans+(bina%2)*pow(10,i);
bina = bina/2;
}
return ans;
}
vector<long long> enum_divisors(long long N) {
vector<long long> res;
for (long long i = 1; i * i <= N; ++i) {
if (N % i == 0) {
res.push_back(i);
// 重複しないならば i の相方である N/i も push
if (N/i != i) res.push_back(N/i);
}
}
// 小さい順に並び替える
sort(res.begin(), res.end());
return res;
}
ll vectorcheck(vector<ll> t,ll key){
auto iter = lower_bound(ALL(t), key);
auto iter2 = upper_bound(ALL(t), key);
if((iter-t.begin())!=(iter2-t.begin())){
return 1;
}
else{
return 0;
}
}
int ctoi(const char c){
switch(c){
case '0': return 0;
case '1': return 1;
case '2': return 2;
case '3': return 3;
case '4': return 4;
case '5': return 5;
case '6': return 6;
case '7': return 7;
case '8': return 8;
case '9': return 9;
default : return -1;
}
}
ll ord(ll a,ll b){
ll ans=0;
while(a%b==0){
ans++;
a/=b;
}
return ans;
}
ll atll(ll a,ll b){
b++;
ll c=expless(a,10);
ll d=c-b;
ll f=1;
for(int i=0;i<d;i++){
f=f*10;
}
a=(a/f);
return a%10;
}
struct BitMatrix {
int H, W;
bitset<MAX_COL> val[MAX_ROW];
BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}
inline bitset<MAX_COL>& operator [] (int i) {return val[i];}
};
int GaussJordan(BitMatrix &A, bool is_extended = false) {
int rank = 0;
for (int col = 0; col < A.W; ++col) {
if (is_extended && col == A.W - 1) break;
int pivot = -1;
for (int row = rank; row < A.H; ++row) {
if (A[row][col]) {
pivot = row;
break;
}
}
if (pivot == -1) continue;
swap(A[pivot], A[rank]);
for (int row = 0; row < A.H; ++row) {
if (row != rank && A[row][col]) A[row] ^= A[rank];
}
++rank;
}
return rank;
}
int pos(const char c){
if('a' <= c && c <= 'z') return (c-'a');
return -1;
}
// グラフの辺の構造体
struct Edge {
int rev, from, to;
FLOW cap, icap;
Edge(int r, int f, int t, FLOW c) : rev(r), from(f), to(t), cap(c), icap(c) {}
friend ostream& operator << (ostream& s, const Edge& E) {
if (E.cap > 0) return s << E.from << "->" << E.to << '(' << E.cap << ')';
else return s;
}
};
// グラフ構造体
struct Graph {
int V;
vector<Edge> list[MAX_V];
Graph(int n = 0) : V(n) { for (int i = 0; i < MAX_V; ++i) list[i].clear(); }
void init(int n = 0) { V = n; for (int i = 0; i < MAX_V; ++i) list[i].clear(); }
void resize(int n = 0) { V = n; }
void reset() { for (int i = 0; i < V; ++i) for (int j = 0; j < int(list[i].size()); ++j) list[i][j].cap = list[i][j].icap; }
inline vector<Edge>& operator [] (int i) { return list[i]; }
Edge &redge(Edge e) {
if (e.from != e.to) return list[e.to][e.rev];
else return list[e.to][e.rev + 1];
}
void addedge(int from, int to, FLOW cap) {
list[from].push_back(Edge((int)list[to].size(), from, to, cap));
list[to].push_back(Edge((int)list[from].size() - 1, to, from, 0));
}
};
// 最大流を求めるサブルーチンたち
static int level[MAX_V];
static int iter[MAX_V];
void dibfs(Graph &G, int s) {
for (int i = 0; i < MAX_V; ++i) level[i] = -1;
level[s] = 0;
queue<int> que;
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (int i = 0; i < int(G[v].size()); ++i) {
Edge &e = G[v][i];
if (level[e.to] < 0 && e.cap > 0) {
level[e.to] = level[v] + 1;
que.push(e.to);
}
}
}
}
FLOW didfs(Graph &G, int v, int t, FLOW f) {
if (v == t) return f;
for (int &i = iter[v]; i < int(G[v].size()); ++i) {
Edge &e = G[v][i], &re = G.redge(e);
if (level[v] < level[e.to] && e.cap > 0) {
FLOW d = didfs(G, e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
re.cap += d;
return d;
}
}
}
return 0;
}
// 最大流を求めるメイン関数
FLOW Dinic(Graph &G, int s, int t) {
FLOW res = 0;
while (true) {
dibfs(G, s);
if (level[t] < 0) return res;
memset(iter, 0, sizeof(iter));
FLOW flow;
while ((flow = didfs(G, s, t, INF)) > 0) {
res += flow;
}
}
}
vector<ll> topological_sort(vector<vector<ll>> &G, vector<ll> &indegree, ll V) {
// トポロジカルソートを記録する配列
vector<ll> sorted_vertices;
// 入次数が0の頂点を発見したら、処理待ち頂点としてキューに追加する
queue<ll> que;
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) {
que.push(i);
}
}
// キューが空になるまで、操作1~3を繰り返す
while (que.empty() == false) {
// キューの先頭の頂点を取り出す
int v = que.front();
que.pop();
// その頂点と隣接している頂点の入次数を減らし、0になればキューに追加
for (int i = 0; i < int(G[v].size()); i++) {
int u = G[v][i];
indegree[u] -= 1;
if (indegree[u] == 0) que.push(u);
}
// 頂点vを配列の末尾に追加する
sorted_vertices.push_back(v);
}
// トポロジカルソートを返す
return sorted_vertices;
}
vector<vector<ll>> multi(vector<vector<ll>> a, vector<vector<ll>> b){
ll n = a.size();
vector<vector<ll>> res(n, vector<ll>(n, 0));
for (ll i = 0; i < n; ++i){
for (ll j = 0; j < n; ++j){
for (ll x = 0; x < n; ++x){
res[i][j] = (res[i][j] + (a[i][x] * b[x][j])) % mod;
}
}
}
return res;
}
vector<vector<ll>> mul_exp(vector<vector<ll>> adj, ll k, ll n){
if (k == 1) return adj;
vector<vector<ll>> res = mul_exp(adj, k / 2, n);
if (k % 2 == 0) return multi(res, res);
else return multi(adj, multi(res, res));
}
struct CHT {
struct Line {
ll slope, yIntercept;
Line(ll slope, ll yIntercept) : slope(slope), yIntercept(yIntercept) {}
ll val(ll x) {
return slope * x + yIntercept;
}
ll intersect(Line y) {
return (y.yIntercept - yIntercept + slope - y.slope - 1) / (slope - y.slope);
}
};
deque<pair<Line, ll>> dq;
void insert(ll slope, ll yIntercept) {
Line newLine(slope, yIntercept);
while (sz(dq) > 1 && dq.back().second >= dq.back().first.intersect(newLine))
dq.pop_back();
if (dq.empty()) {
dq.emplace_back(newLine, 0);
return;
}
dq.emplace_back(newLine, dq.back().first.intersect(newLine));
}
ll query(ll x) {
while (sz(dq) > 1) {
if (dq[1].second <= x) dq.pop_front();
else break;
}
return dq[0].first.val(x);
}
ll query2(ll x) {
auto qry = *lower_bound(dq.rbegin(), dq.rend(),
make_pair(Line(0, 0), x),
[&](const pair<Line, int> &a, const pair<Line, int> &b) {
return a.second > b.second;
});
return qry.first.val(x);
}
};
template <typename T>
int compress(vector<T> x, map<T, int> &zip, vector<int> &unzip) {
sort(x.begin(), x.end());
x.erase(unique(x.begin(), x.end()), x.end());
for (int i = 0; i < x.size(); i++) {
zip[x[i]] = i;
unzip[i] = x[i];
}
return x.size();
}
long long modlog(long long x,long long y,long long MOD){
x %= MOD;
y %= MOD;
long long H = sqrt(MOD);
vector<pair<long long,long long>> baby(H);
// Baby-step
long long Z = y;
for(long long a=0;a<H;a++){ //yx^(H-1)
baby[a] = make_pair(Z,a);
Z = (Z*x) % MOD;
}
sort(baby.begin(),baby.end());
// Giant step
long long xH=1;
for(int i=0;i<H;i++) xH = (xH*x) % MOD;
long long xaH = 1;
for(int a=1;a<=(MOD/H)+1;a++){
xaH = (xaH*xH) % MOD;
auto itr = lower_bound(baby.begin(),baby.end(),make_pair(xaH+1,0LL));
if(itr->second==H) continue;
itr--;
if(itr->first==xaH) return a*H - itr->second;
}
return -1;
}
vector<pair<ll,ll>> lp(vector<ll> a){
sor(a);
ll x=a.at(0);
ll y=1;
vector<pair<ll,ll>> ans;
for(int i=1;i<int(a.size());i++){
if(a.at(i)!=a.at(i-1)){
ans.push_back({x,y});
x=a.at(i);
y=1;
}
else{
y++;
}
}
if(y!=0){
ans.push_back({x,y});
}
return ans;
}
typedef unsigned long long ull;
#define B1 100000007
#define B2 1000000007
bool rolling_hash(string const& S, int t_start, int m){
int s_start = t_start + m;
// B^mを用意する
ull pow_B_m_1 = 1, pow_B_m_2 = 1;
for(int k = 0; k < m; k++){
pow_B_m_1 *= B1, pow_B_m_2 *= B2;
}
// sとtの先頭m文字のハッシュ値sh,thを計算
ull sh1 = 0, sh2 = 0, th1 = 0, th2 = 0;
for(int k = 0; k < m; k++){
th1 = th1 * B1 + S[t_start + k], th2 = th2 * B2 + S[t_start + k];
sh1 = sh1 * B1 + S[s_start + k], sh2 = sh2 * B2 + S[s_start + k];
}
// sをずらしてハッシュ値を更新
for(int k = 0; s_start + k < int(S.length()); k++){
if(sh1 == th1 && sh2 == th2) return true;
if(k + s_start < int(S.length())){
sh1 = sh1 * B1 + S[s_start + m + k] - S[s_start + k] * pow_B_m_1;
sh2 = sh2 * B2 + S[s_start + m + k] - S[s_start + k] * pow_B_m_2;
}
}
return false;
}
constexpr double PI = acosl(-1);
struct Comp {
double real, imag;
Comp(double real = 0, double imag = 0) : real(real), imag(imag) {}
friend inline ostream& operator << (ostream &s, const Comp &c) {
return s << '<' << c.real << ',' << c.imag << '>';
}
inline Comp operator + (const Comp &c) {
return {real + c.real, imag + c.imag};
}
inline Comp operator - (const Comp &c) {
return {real - c.real, imag - c.imag};
}
inline Comp operator * (const Comp &c) {
return {real * c.real - imag * c.imag,
real * c.imag + imag * c.real};
}
inline Comp operator * (double a) {
return {real * a, imag * a};
}
inline Comp operator / (double a) {
return {real / a, imag / a};
}
};
// FFT
void trans(vector<Comp> &v, bool inv = false) {
int n = SIZE(v);
for (int i = 0, j = 1; j < n-1; j++) {
for (int k = n>>1; k > (i ^= k); k >>= 1);
if (i > j) swap(v[i], v[j]);
}
for (int t = 2; t <= n; t <<= 1) {
double ang = acosl(-1.0) * 2 / t;
if (inv) ang = -ang;
for (int i = 0; i < n; i += t) {
REP(j, t/2) {
Comp w = {cos(ang * j), sin(ang * j)};
int j1 = i + j, j2 = i + j + t/2;
Comp c1 = v[j1], c2 = v[j2] * w;
v[j1] = c1 + c2;
v[j2] = c1 - c2;
}
}
}
if (inv) REP(i, n) v[i] = v[i]/n;
}
// A * B
vector<ll> mult(const vector<ll> &A,
const vector<ll> &B) {
int size_a = 1; while (size_a < SIZE(A)) size_a <<= 1;
int size_b = 1; while (size_b < SIZE(B)) size_b <<= 1;
int size_fft = max(size_a, size_b) << 1;
vector<Comp> cA(size_fft), cB(size_fft), cC(size_fft);
for (int i = 0; i < SIZE(A); ++i) cA[i] = {(double)A[i], 0};
for (int i = 0; i < SIZE(B); ++i) cB[i] = {(double)B[i], 0};
trans(cA); trans(cB);
REP(i, size_fft) cC[i] = cA[i] * cB[i];
trans(cC, true);
vector<ll> res(SIZE(A) + SIZE(B) - 1);
for (int i = 0; i < SIZE(res); ++i) {
res[i] = (ll)(cC[i].real + 0.5);
}
return res;
}
template<typename T>
struct BellmanFord {
struct Vertex {
int to; T cost;
Vertex (int to_, T cost_) : to(to_), cost(cost_) {}
};
T INF;
const int n;
vector<vector<Vertex>> Graph, invGraph;
vector<T> dt;
vector<bool> reach;
void reachable(const int now, vector<bool> &seen){
if(seen[now]) return;
seen[now] = true;
for(const Vertex nxt : Graph[now]) reachable(nxt.to, seen);
}
public:
bool loop = false;
BellmanFord (const int n_, const T INF_ = numeric_limits<T>::max()/2)
: INF(INF_), n(n_), Graph(n_), invGraph(n_), dt(n, INF), reach(n, true) {}
T operator [] (const int i) { return dt[i]; }
void AddEdge(const int from, const int to, const T cost){
Graph[from].push_back(Vertex(to, cost));
}
void Build (const int from){
dt[from] = 0;
for(int i = 0; i < n; i++){
bool update = false;
for(int now = 0; now < n; now++){
if(!reach[now]) continue;
for(const Vertex nxt : Graph[now]){
if(!reach[nxt.to] or dt[now] == INF) continue;
if(dt[nxt.to] > dt[now] + nxt.cost){
dt[nxt.to] = dt[now] + nxt.cost;
update = true;
if(i == n-1) loop = true;
}
}
}
if(!update) break;
}
}
void Build (const int from, const int to){
for(int i = 0; i < n; i++){
vector<bool> seen(n, false);
reachable(i, seen);
reach[i] = seen[to];
}
Build(from);
}
};
ll P(ll a,ll b){
if(a<0||b<0||a<b) return -1;
ll c=a-b;
c=modPow(fac[c],mod-2,mod);
a=fac[a];
a*=c;
a%=mod;
return a;
}
class UnionFind {
public:
vector <ll> par; // 各元の親を表す配列
vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)
// Constructor
UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
}
void init(ll sz_) {
par.resize(sz_);
siz.assign(sz_, 1LL); // resize だとなぜか初期化されなかった
for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
}
// Member Function
// Find
ll root(ll x) { // 根の検索
while (par[x] != x) {
x = par[x] = par[par[x]]; // x の親の親を x の親とする
}
return x;
}
// Union(Unite, Merge)
bool merge(ll x, ll y) {
x = root(x);
y = root(y);
if (x == y) return false;
// merge technique（データ構造をマージするテク．小を大にくっつける）
if (siz[x] < siz[y]) swap(x, y);
siz[x] += siz[y];
par[y] = x;
return true;
}
bool issame(ll x, ll y) { // 連結判定
return root(x) == root(y);
}
ll size(ll x) { // 素集合のサイズ
return siz[root(x)];
}
};
template<class Monoid, class Action> struct SegTree {
using FuncMonoid = function< Monoid(Monoid, Monoid) >;
using FuncAction = function< void(Monoid&, Action) >;
using FuncLazy = function< void(Action&, Action) >;
FuncMonoid FM;
FuncAction FA;
FuncLazy FL;
Monoid IDENTITY_MONOID;
Action IDENTITY_LAZY;
int SIZE, HEIGHT;
vector<Monoid> dat;
vector<Action> lazy;
SegTree() { }
SegTree(int n, const FuncMonoid fm, const FuncAction fa, const FuncLazy fl,
const Monoid &identity_monoid, const Action &identity_lazy)
: FM(fm), FA(fa), FL(fl),
IDENTITY_MONOID(identity_monoid), IDENTITY_LAZY(identity_lazy) {
SIZE = 1, HEIGHT = 0;
while (SIZE < n) SIZE <<= 1, ++HEIGHT;
dat.assign(SIZE * 2, IDENTITY_MONOID);
lazy.assign(SIZE * 2, IDENTITY_LAZY);
}
void init(int n, const FuncMonoid fm, const FuncAction fa, const FuncLazy fl,
const Monoid &identity_monoid, const Action &identity_lazy) {
FM = fm, FA = fa, FL = fl;
IDENTITY_MONOID = identity_monoid, IDENTITY_LAZY = identity_lazy;
SIZE = 1; HEIGHT = 0;
while (SIZE < n) SIZE <<= 1, ++HEIGHT;
dat.assign(SIZE * 2, IDENTITY_MONOID);
lazy.assign(SIZE * 2, IDENTITY_LAZY);
}
// set, a is 0-indexed
void set(int a, const Monoid &v) { dat[a + SIZE] = v; }
void build() {
for (int k = SIZE - 1; k > 0; --k)
dat[k] = FM(dat[k*2], dat[k*2+1]);
}
// update [a, b)
inline void evaluate(int k) {
if (lazy[k] == IDENTITY_LAZY) return;
if (k < SIZE) FL(lazy[k*2], lazy[k]), FL(lazy[k*2+1], lazy[k]);
FA(dat[k], lazy[k]);
lazy[k] = IDENTITY_LAZY;
}
inline void update(int a, int b, const Action &v, int k, int l, int r) {
evaluate(k);
if (a <= l && r <= b) FL(lazy[k], v), evaluate(k);
else if (a < r && l < b) {
update(a, b, v, k*2, l, (l+r)>>1);
update(a, b, v, k*2+1, (l+r)>>1, r);
dat[k] = FM(dat[k*2], dat[k*2+1]);
}
}
inline void update(int a, int b, const Action &v) {
update(a, b, v, 1, 0, SIZE);
}
// get [a, b)
inline Monoid get(int a, int b, int k, int l, int r) {
evaluate(k);
if (a <= l && r <= b)
return dat[k];
else if (a < r && l < b)
return FM(get(a, b, k*2, l, (l+r)>>1),
get(a, b, k*2+1, (l+r)>>1, r));
else
return IDENTITY_MONOID;
}
inline Monoid get(int a, int b) {
return get(a, b, 1, 0, SIZE);
}
inline Monoid operator [] (int a) {
return get(a, a + 1);
}
// debug
void print() {
for (int i = 0; i < SIZE; ++i) {
if (i) cout << ",";
cout << (*this)[i];
}
cout << endl;
}
};
template< typename T >
struct FormalPowerSeries : vector< T > {
using vector< T >::vector;
using P = FormalPowerSeries;
using MULT = function< P(P, P) >;
static MULT &get_mult() {
static MULT mult = nullptr;
return mult;
}
static void set_fft(MULT f) {
get_mult() = f;
}
FormalPowerSeries(const vector< T > &v) : FormalPowerSeries(v.begin(), v.end()) {}
P operator+(const P &r) const { return P(*this) += r; }
P operator-(const P &r) const { return P(*this) -= r; }
P operator*(const P &r) const { return P(*this) *= r; }
P operator*(const T &v) const { return P(*this) *= v; }
P operator/(const P &r) const { return P(*this) /= r; }
P &operator+=(const P &r) {
if(r.size() > this->size()) this->resize(r.size());
for(int i = 0; i < r.size(); i++) (*this)[i] += r[i];
return *this;
}
P &operator-=(const P &r) {
if(r.size() > this->size()) this->resize(r.size());
for(int i = 0; i < r.size(); i++) (*this)[i] -= r[i];
return *this;
}
P &operator*=(const T &v) {
const int n = (int) this->size();
for(int k = 0; k < n; k++) (*this)[k] *= v;
return *this;
}
P &operator*=(const P &r) {
if(this->empty() || r.empty()) {
this->clear();
return *this;
}
assert(get_mult() != nullptr);
auto ret = get_mult()(*this, r);
this->resize(ret.size());
for(int k = 0; k < ret.size(); k++) (*this)[k] = ret[k];
return *this;
}
P operator-() const {
P ret(this->size());
for(int i = 0; i < this->size(); i++) ret[i] = -(*this)[i];
return ret;
}
P &operator/=(const P &r) {
return *this *= r.inverse();
}
P pre(int sz) const {
return P(begin(*this), begin(*this) + min((int) this->size(), sz));
}
P rev() const {
P ret(*this);
reverse(begin(ret), end(ret));
return ret;
}
P diff() const {
const int n = (int) this->size();
P ret(max(0, n - 1));
for(int i = 1; i < n; i++) ret[i] = (*this)[i] * T(i);
return ret;
}
P integral() const {
const int n = (int) this->size();
P ret(n + 1);
ret[0] = T(0);
for(int i = 0; i < n; i++) ret[i + 1] = (*this)[i] / T(i + 1);
}
// F(0) must not be 0
P inv(int deg = -1) const {
assert(((*this)[0]) != T(0));
const int n = (int) this->size();
if(deg == -1) deg = n;
P ret({T(1) / (*this)[0]});
for(int i = 1; i < deg; i <<= 1) {
ret = (ret * T(2) - ret * ret * pre(i << 1)).pre(i << 1);
}
return ret.pre(deg);
}
// F(0) must be 1
P log(int deg = -1) const {
assert((*this)[0] == 1);
const int n = (int) this->size();
if(deg == -1) deg = n;
return (this->diff() * this->inv(deg)).integral().pre(deg);
}
// F(0) must be 1
P sqrt(int deg = -1) const {
assert((*this)[0] == T(1));
const int n = (int) this->size();
if(deg == -1) deg = n;
P ret({T(1)});
T inv2 = T(1) / T(2);
for(int i = 1; i < deg; i <<= 1) {
ret = (ret + pre(i << 1) * ret.inv(i << 1)).pre(i << 1) * 2;
}
return ret.pre(deg);
}
// F(0) must be 0
P exp(int deg) const {
assert((*this)[0] == T(0));
const int n = (int) this->size();
P ret({T(1)}), g({T(1)});
for(int i = 1; i < deg; i <<= 1) {
ret = (ret * (pre(1 << i) + g) - ret.log(1 << i)).pre(1 << i);
}
return ret.pre(deg);
}
};
namespace FastFourierTransform {
using real = double;
struct C {
real x, y;
C() : x(0), y(0) {}
C(real x, real y) : x(x), y(y) {}
inline C operator+(const C &c) const { return C(x + c.x, y + c.y); }
inline C operator-(const C &c) const { return C(x - c.x, y - c.y); }
inline C operator*(const C &c) const { return C(x * c.x - y * c.y, x * c.y + y * c.x); }
inline C conj() const { return C(x, -y); }
};
const real PI = acosl(-1);
int base = 1;
vector< C > rts = {{0, 0},
{1, 0}};
vector< int > rev = {0, 1};
void ensure_base(int nbase) {
if(nbase <= base) return;
rev.resize(1 << nbase);
rts.resize(1 << nbase);
for(int i = 0; i < (1 << nbase); i++) {
rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
}
while(base < nbase) {
real angle = PI * 2.0 / (1 << (base + 1));
for(int i = 1 << (base - 1); i < (1 << base); i++) {
rts[i << 1] = rts[i];
real angle_i = angle * (2 * i + 1 - (1 << base));
rts[(i << 1) + 1] = C(cos(angle_i), sin(angle_i));
}
++base;
}
}
void fft(vector< C > &a, int n) {
assert((n & (n - 1)) == 0);
int zeros = __builtin_ctz(n);
ensure_base(zeros);
int shift = base - zeros;
for(int i = 0; i < n; i++) {
if(i < (rev[i] >> shift)) {
swap(a[i], a[rev[i] >> shift]);
}
}
for(int k = 1; k < n; k <<= 1) {
for(int i = 0; i < n; i += 2 * k) {
for(int j = 0; j < k; j++) {
C z = a[i + j + k] * rts[j + k];
a[i + j + k] = a[i + j] - z;
a[i + j] = a[i + j] + z;
}
}
}
}
vector< int64_t > multiply(const vector< int > &a, const vector< int > &b) {
int need = (int) a.size() + (int) b.size() - 1;
int nbase = 1;
while((1 << nbase) < need) nbase++;
ensure_base(nbase);
int sz = 1 << nbase;
vector< C > fa(sz);
for(int i = 0; i < sz; i++) {
int x = (i < (int) a.size() ? a[i] : 0);
int y = (i < (int) b.size() ? b[i] : 0);
fa[i] = C(x, y);
}
fft(fa, sz);
C r(0, -0.25 / (sz >> 1)), s(0, 1), t(0.5, 0);
for(int i = 0; i <= (sz >> 1); i++) {
int j = (sz - i) & (sz - 1);
C z = (fa[j] * fa[j] - (fa[i] * fa[i]).conj()) * r;
fa[j] = (fa[i] * fa[i] - (fa[j] * fa[j]).conj()) * r;
fa[i] = z;
}
for(int i = 0; i < (sz >> 1); i++) {
C A0 = (fa[i] + fa[i + (sz >> 1)]) * t;
C A1 = (fa[i] - fa[i + (sz >> 1)]) * t * rts[(sz >> 1) + i];
fa[i] = A0 + A1 * s;
}
fft(fa, sz >> 1);
vector< int64_t > ret(need);
for(int i = 0; i < need; i++) {
ret[i] = llround(i & 1 ? fa[i >> 1].y : fa[i >> 1].x);
}
return ret;
}
};
template< typename T >
struct ArbitraryModConvolution {
using real = FastFourierTransform::real;
using C = FastFourierTransform::C;
ArbitraryModConvolution() = default;
vector< T > multiply(const vector< T > &a, const vector< T > &b, int need = -1) {
if(need == -1) need = a.size() + b.size() - 1;
int nbase = 0;
while((1 << nbase) < need) nbase++;
FastFourierTransform::ensure_base(nbase);
int sz = 1 << nbase;
vector< C > fa(sz);
for(int i = 0; i < a.size(); i++) {
fa[i] = C(a[i].x & ((1 << 15) - 1), a[i].x >> 15);
}
fft(fa, sz);
vector< C > fb(sz);
if(a == b) {
fb = fa;
} else {
for(int i = 0; i < b.size(); i++) {
fb[i] = C(b[i].x & ((1 << 15) - 1), b[i].x >> 15);
}
fft(fb, sz);
}
real ratio = 0.25 / sz;
C r2(0, -1), r3(ratio, 0), r4(0, -ratio), r5(0, 1);
for(int i = 0; i <= (sz >> 1); i++) {
int j = (sz - i) & (sz - 1);
C a1 = (fa[i] + fa[j].conj());
C a2 = (fa[i] - fa[j].conj()) * r2;
C b1 = (fb[i] + fb[j].conj()) * r3;
C b2 = (fb[i] - fb[j].conj()) * r4;
if(i != j) {
C c1 = (fa[j] + fa[i].conj());
C c2 = (fa[j] - fa[i].conj()) * r2;
C d1 = (fb[j] + fb[i].conj()) * r3;
C d2 = (fb[j] - fb[i].conj()) * r4;
fa[i] = c1 * d1 + c2 * d2 * r5;
fb[i] = c1 * d2 + c2 * d1;
}
fa[j] = a1 * b1 + a2 * b2 * r5;
fb[j] = a1 * b2 + a2 * b1;
}
fft(fa, sz);
fft(fb, sz);
vector< T > ret(need);
for(int i = 0; i < need; i++) {
int64_t aa = llround(fa[i].x);
int64_t bb = llround(fb[i].x);
int64_t cc = llround(fa[i].y);
aa = T(aa).x, bb = T(bb).x, cc = T(cc).x;
ret[i] = aa + (bb << 15) + (cc << 30);
}
return ret;
}
};
template< int mod >
struct ModInt {
int x;
ModInt() : x(0) {}
ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
ModInt &operator+=(const ModInt &p) {
if((x += p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator-=(const ModInt &p) {
if((x += mod - p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator*=(const ModInt &p) {
x = (int) (1LL * x * p.x % mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt operator-() const { return ModInt(-x); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return x == p.x; }
bool operator!=(const ModInt &p) const { return x != p.x; }
ModInt inverse() const {
int a = x, b = mod, u = 1, v = 0, t;
while(b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ModInt(u);
}
ModInt pow(int64_t n) const {
ModInt ret(1), mul(x);
while(n > 0) {
if(n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ModInt &p) {
return os << p.x;
}
friend istream &operator>>(istream &is, ModInt &a) {
int64_t t;
is >> t;
a = ModInt< mod >(t);
return (is);
}
};
using modint = ModInt< mod >;
int main() {
/* mod は 1e9+7 */
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout<< fixed << setprecision(10);
ll n;
cin>>n;
ll ans=0;
ll tmp=1;
for(ll i=2;i<=n;i++){
tmp*=i;
tmp%=mod;
}
ans=-tmp;
ans%=mod;
ans+=mod;
ans%=mod;
for(ll i=n+1;i<=n+2;i++){
tmp*=i;
tmp%=mod;
}
tmp*=modPow(6,mod-2,mod);
tmp%=mod;
ans+=tmp;
ans%=mod;
cout<<ans<<endl;
}