讲下赛时思路吧，没题解好想：

#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const LL P = 1e9 + 7;
 
struct node {
	LL a[2][2];
	node() {
		memset(a, 0, sizeof(a));
	}
};
 
node operator*(node na, node nb) {
	node res;
	for (int i = 0;i <= 1; i ++) {
		for (int j = 0; j <= 1; j ++) {
			for (int k = 0; k <= 1; k ++) {
				res.a[i][j] = (res.a[i][j] + na.a[i][k] * nb.a[k][j] % P) % P ;
			}
		}
	}
	return res;
}
 
node mq_pow(node a, LL b) {
	node c;
	c.a[0][0] = c.a[1][1] = 1;
	while (b) {
		if (b & 1) {
			c = c * a;
		}
		a = a * a;
		b >>= 1;
	}
	return c;
}
 
LL q_pow(LL a, LL b) {
	LL c = 1;
	while (b) {
		if (b & 1) {
			c = c * a % P;
		}
		a = a * a % P;
		b >>= 1;
	}
	return c;
}
 
 
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	LL n, K;
	cin >> n >> K;
	
	if (K < n) {
		cout << "0\n";
		return 0;
	}
	node t;
	t.a[0][0] = 1; t.a[0][1] = 1;
	node tt;
	tt.a[0][0] = tt.a[0][1] = tt.a[1][0] = 1;
	node ans = t * mq_pow(tt, n - 1);
	LL dow = q_pow(K, n);
	dow = q_pow(dow, P - 2);
	
	
	cout << (ans.a[0][0] * dow % P) << "\n";
	
	return 0;
}