結果

問題 No.557 点対称
ユーザー beet
提出日時 2017-08-11 22:35:29
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,911 bytes
コンパイル時間 1,376 ms
コンパイル使用メモリ 161,368 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-12 21:18:02
合計ジャッジ時間 2,241 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define int long long

#define MOD 1000000007
#define MAX_N 100000
#define MAX_P 200005
int fact[MAX_P];
int extgcd(int a,int b,int& x,int& y){
  int d=a;
  if(b!=0){
    d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1;y=0;
  }
  return d;
}
int mod_inverse(int a,int m){
  int x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}

int euler_phi(int n){
  int res=n;
  for(int i=2;i*i<=n;i++){
    if(n%i==0){
      res=res/i*(i-1);
      for(;n%i==0;n/=i);
    }
  }
  if(n!=1) res=res/n*(n-1);
  return res;
}

int euler[MAX_N];

void euler_phi2(){
  for(int i=0;i<MAX_N;i++) euler[i]=i;
  for(int i=2;i<MAX_N;i++){
    if(euler[i]==i){
      for(int j=i;j<MAX_N;j+=i) euler[j]=euler[j]/i*(i-1);
    }
  }
}

int mod_pow(int x,int n,int mod){
  int res=1;
  while(n>0){
    if(n&1) (res*=x)%=mod;
    (x*=x)%=mod;
    n>>=1;
  }
  return res;
}

void init(int p){
  fact[0]=1;
  for(int i=1;i<MAX_P;i++) fact[i]=(fact[i-1]*i)%p;
}

int mod_fact(int n,int p,int& e){
  e=0;
  if(n==0) return 1;
  int res=mod_fact(n/p,p,e);
  e+=n/p;
  if(n/p%2!=0)return res*(p-fact[n%p]) %p;
  return res*fact[n%p]%p;
} 
int mod_comb(int n,int k,int p){
  if(n==k||k==0) return 1;
  int e1,e2,e3;
  int a1=mod_fact(n,p,e1),a2=mod_fact(k,p,e2),a3=mod_fact(n-k,p,e3);
  if(e1>e2+e3) return 0;
  return a1*mod_inverse(a2*a3%p,p)%p;
}

int mod_comb2(int n,int k,int mod){
  int res=1;
  for(int i=0;i<k;i++){
    res*=n-i;
    res%=mod;
    res*=mod_inverse(i+1,mod);
    res%=mod;
  }
  return res;
}

int montmort(int n,int mod){
  int res=0,inv=1;
  for(int k=2;k<=n;k++){
    (inv*=mod_inverse(k,mod))%=mod;
    if(k%2 ) (res+=mod-inv)%=mod;
    else (res+=inv)%=mod;
  }
  for(int i=1;i<=n;i++)
    (res*=i)%=mod;
  return res;
}


signed main(){
  int n;
  cin>>n;
  int ans=4*mod_pow(5,n/2-1,MOD)%MOD;
  if(n%2) ans=ans*3%MOD;
  if(n==1) ans=2;
  cout<<ans<<endl;
  return 0;
}
0