class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回将这个数n拆成两个自然数之和一共有多少种拆法（符合规则）。
     * @param n int整型 代表题意中的n
     * @return int整型
     */
    int solve(int n) {
        // write code here
        return (n-1)/2;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回总体积为V若干物品的最大总重量，如果g存在选择若干物品总体积为V的情况，返回-1
     * @param v int整型vector 
     * @param g int整型vector 
     * @param V int整型 
     * @return int整型
     */
    int ans,n,vv;
    vector<int> V,G;
    void dfs(int now,int v,int g){
        if (now==n){
            if (v==vv&&g>ans) ans=g;
            return;
        }
        dfs(now+1,v,g);
        if (v+V[now]<=vv) dfs(now+1,v+V[now],g+G[now]);
    }
    int Maximumweight(vector<int>& v, vector<int>& g, int _vv) {
        // write code here
        ans=-1;
        vv=_vv;
        n=v.size();
        for(int i=0;i<n;++i){
            V.push_back(v[i]);
            G.push_back(g[i]);
        }
        dfs(0,0,0);
        return ans;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 给定一个字符串s，返回具有相同前缀后缀的子串的第二大长度，反之，返回-1即可。
     * @param s string字符串 代表题意中的字符串s
     * @return int整型
     */
    int f[1100000];
    int solve(string s) {
        // write code here
        int j=0;
        int n=s.length();
        f[1]=0;
        int ans=0;
        for(int i=2;i<=n;++i){
            while (j&&s[i-1]!=s[j]) j=f[j];
            if (s[i-1]==s[j]) ++j;
            f[i]=j;
            //if (f[i]>ans) ans=f[i];
        }
        ans=f[n];
        if (ans==0) ans=-1;
        return ans;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 有n个城市
     * @param m int整型 有m条路径
     * @param s int整型 起始城市坐标
     * @param t int整型 终点城市坐标
     * @param edge int整型vector<vector<>> 边的格式如下:[[u1,v1,a1,b1],[u2,v2,a2,b2],...]
     * @return int整型
     */
    const int p=1000000007;
    long double f[510],fac[1110];
    long long g[510],C[1110][1110];
    void relax(int u,int v,int a,int b){
        if (f[u]+fac[a]-fac[b]-fac[a-b]<f[v]){
            f[v]=f[u]+fac[a]-fac[b]-fac[a-b];
            g[v]=g[u]*C[a][b]%p;
        }
    }
    int minDist(int n, int m, int s, int t, vector<vector<int> >& edge) {
        // write code here
        for(int i=1;i<=1000;++i) fac[i]=fac[i-1]+log(i);
        C[0][0]=1;//!!!!!!!!!!!!
        for(int i=1;i<=1000;++i){
            C[i][0]=1;
            for(int j=1;j<=i;++j){
                C[i][j]=C[i-1][j]+C[i-1][j-1];
                if (C[i][j]>=p) C[i][j]-=p;
            }
        }
        for(int i=1;i<=n;++i) f[i]=1e50;
        f[s]=0;
        g[s]=1;
        for(int i=1;i<=n;++i){
            for(int j=0;j<edge.size();++j){
                relax(edge[j][0],edge[j][1],edge[j][2],edge[j][3]);
                relax(edge[j][1],edge[j][0],edge[j][2],edge[j][3]);
            }
        }
        return g[t];
    }
};