求N个点中取偶数个点相连的种类数并取模

现有N个点从1到N编号，每个点只可以与其余一个点相连或者不相连，即对于任意一个N最多有【N/2】取整对点相连，求N个点如何相连的种类数并取模。
要求输入N和m，输出种类数mol m 后的结果。
数据N<=10000000，2<=m<=10^13。
例如N分别等于2,3,4,5时种类数分别为2,4,10,26。

#include<stdio.h>
long long m;
int main()
{ 
  long long f(int x,int y);
  long long t,i,j,n,sum=1;
  scanf("%d%d",&n,&m);
  for(i=1;i<=n/2;i++)
     {
     sum+=f(n,i)%m;
     }
  printf("%lld",sum%m);
return 0;
}
long long f(int x,int y)
{   
     long long i;
     if(y==1) 
     return x*(x-1)/2;
     else
     return (f(x,y-1)*(x-2*y+2)*(x-2*y+1))/(2*y);
}

用排列组合递归的思想写出了一个代码，但对于很大的N该代码运算会超时或答案错误，想找到取余或者运算的优化方法。

试一下我的代码

#include <stdio.h>

long long func(long long n, long long m)
{
    long long r1 = 1;
    long long r2 = 1;
    long long r = 0;

    for (long long i = 0; i < n; ++i) {
        r = (r2 * i % m + r1 % m) % m;
        r2 = r1;
        r1 = r;
    }

    return r;
    // if (n < 2) {
    //     return 1;
    // }
    // return func(n - 1) + (n - 1) * func(n - 2);
}

int main()
{
    long long n, m;

    scanf("%lld%lld", &n, &m);

    printf("%lld", func(n, m));
}

10000000 10000000000000
2767024144384

首先，既然告诉你了只要模，那么这个数最大到底多大就不再重要了
你不要真的用long long来存它，直接
sum%=m
就可以了
这个要在循环里面做。
其次，既然题目只问可能的数量，而不是让你输出每种可能
那么不要写递归，N取2的组合数量，套公式就行了，别真的去遍历数啊
最后，循环次数应该i=2;i<=n/2;i+=2，不要再去计算奇数个连接，不可能有奇数个连接

建立一个二叉树，我们约定左结点表示选择连，右节点表示不连