$$\nu _{p}(n!)=\sum _{{i=1}}^{{\infty }}\left\lfloor {\frac {n}{p^{i}}}\right\rfloor$$

$\nu_p(n)$表示 $n$的标准分解里 $p$的指数，或者如果 $p^k||n$,$\nu_p(n)=k$

$$\nu_{p}(n!)={\frac {n-s_{p}(n)}{p-1}}$$

$$\nu_2\binom{n}{a_1,a_2,…,a_k} = 0$$

$$\nu_2(n!)=\nu_2(a_1!)+ \cdots + \nu_2(a_k!)$$

$$s_2(n)=s_2(a_1)+ \cdots + s_2(a_k)$$

$Q.E.D.$

$$f_{i,S} = \sum_{x \subseteq S} \frac {1}{x!}f_{i-1,S – x}$$

//HomuraCat codes it!
#include<time.h>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<queue>
#include<vector>
#include<set>
#include<cstdlib>
#include<iostream>
#include<utility>
#include<map>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define eps 1e-4
#define lowbit(x) (x & -x)
#define N 263005
#define clr(arr) memset(arr, 0, sizeof arr)
#define bset std::bitset<N>
#define pi std::pair<int, int>
{
ll x = 0; bool flag = 0; char ch = getchar();
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') flag = 1, ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
if (flag) x = -x; return x;
}
inline ll qabs (ll x) { return x < 0 ? -x : x; }
int P;
inline ll qpow (ll x, int y)
{
ll ret = 1;
while (y)
{
if (y & 1) ret = ret * x % P;
x = x * x % P;
y >>= 1;
}
return ret;
}
int n, m, f[19][N], g[19][N], h[19][N];
void add (int &x, int y)
{
x = x + y;
if (x >= P) x -= y;
}
void fwt(int *a,int limit,int op){
for(int mid=1;mid<limit;mid<<=1){
for(int R=(mid<<1),i=0;i<limit;i+=R){
for(int j=0;j<mid;++j){
if(op==1) a[i+j+mid]=(a[i+j]+a[i+j+mid])%P;
else a[i+j+mid]=(a[i+j+mid]-a[i+j]+P)%P;
}
}
}
}
int fac[N], ifac[N];
int limit = 1, up = 0;
void mul (int a[][N], int b[][N])
{
fo (i, 0, up)
fo (j, 0, i)
fo (k, 0, limit - 1)
h[i][k] = (h[i][k] + 1ll * a[j][k] * b[i - j][k]) % P;
fo (i, 0, up) fo (k, 0, limit - 1) a[i][k] = h[i][k], h[i][k] = 0;
}
void pow_m(int m)
{
fo (i, 0, up) fwt(f[i], limit, 1);
fo (i, 0, up) fwt(g[i], limit, 1);
while (m)
{
if (m & 1) mul(f, g);
m >>= 1;
mul(g, g);
}
fo (i, 0, up) fwt(f[i], limit, -1);
}
int main ()
{
ll ans = qpow(m, n);
if (n & 1)
{
printf("%lld\n", ans);
return 0;
}
while (limit <= n) limit <<= 1, up++;
fac[0] = ifac[0] = 1;
fo (i, 1, limit) fac[i] = 1ll * fac[i - 1] * i % P;
ifac[limit] = qpow(fac[limit], P - 2);
fd (i, limit - 1, 1) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
f[0][0] = 1;
fo (i, 0, limit - 1) g[__builtin_popcount(i)][i] = ifac[i];
pow_m(m);
ans = (ans - 1ll * f[__builtin_popcount(n)][n] * fac[n] % P + P) % P;
printf("%lld\n", ans % P);
return 0;
}