Given the following C code and unoptimized assembly code, your task is to generate highly optimized x86-64 assembly code.
C Code:

```c
#include <stdio.h>
#include <stdlib.h>
#define int long long
#define p (int)(1e9 + 7)

int MOD(int a){
	a %= p;
	return a >= 0 ? a : a + p;
}

int power(int a, int N){
	if(N == 0){
		return 1;
	}
	else if(N % 2 == 0){
		return power(MOD(a * a), N / 2);
	}
	else{
		return MOD(a * power(a, N - 1));
	}
}

int inverse(int a){
	return power(a, p - 2);
}

int *fact, *fact_inv;

int comb(int n, int k){
	if(k < 0 || n < k || n < 0){
		return 0;
	}
	else{
		return MOD(fact[n] * MOD(fact_inv[k] * fact_inv[n - k]));
	}
}

signed main(){
	int B, W, i;
	scanf("%lld%lld", &B, &W);
	fact = (int *)malloc(sizeof(int) * (B + W + 1));
	fact[0] = 1;
	for(i = 1; i <= B + W; i++){
		fact[i] = MOD(fact[i - 1] * i);
	}
	fact_inv = (int *)malloc(sizeof(int) * (B + W + 1));
	for(i = 0; i <= B + W; i++){
		fact_inv[i] = inverse(fact[i]);
	}
	int *a = (int *)malloc(sizeof(int) * (B + W + 1));
	int *b = (int *)malloc(sizeof(int) * (B + W + 1));
	int *c = (int *)malloc(sizeof(int) * (B + W + 1));
	for(i = 0; i < W; i++){
		a[i] = 0;
	}
	for(i = W; i < B + W; i++){
		a[i] = MOD(a[i - 1] + comb(i - 1, W - 1) * inverse(power(2, i)));
	}
	a[B + W] = 1;

	for(i = 0; i < B; i++){
		b[i] = 0;
	}
	for(i = B; i < B + W; i++){
		b[i] = MOD(b[i - 1] + comb(i - 1, B - 1) * inverse(power(2, i)));
	}
	b[B + W] = 1;

	for(i = 0; i < B + W; i++){
		c[i] = MOD(1 - a[i] - b[i]);
	}
	c[B + W] = 0;

/*	for(i = 0; i <= B + W; i++){
		printf("a[%lld] = %lld\n", i, a[i]);
	}
	printf("\n");

	for(i = 0; i <= B + W; i++){
		printf("b[%lld] = %lld\n", i, b[i]);
	}
	printf("\n");

	for(i = 0; i <= B + W; i++){
		printf("c[%lld] = %lld\n", i, c[i]);
	}
	printf("\n");
*/
	for(i = 1; i <= B + W; i++){
		printf("%lld\n", MOD(a[i - 1] + inverse(2) * c[i - 1]));
	}
	return 0;
}```

Unoptimized Assembly Code:

```assembly
	.file	"temp.c"
	.text
	.globl	MOD
	.type	MOD, @function
MOD:
.LFB6:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, -8(%rbp)
	movq	-8(%rbp), %rcx
	movabsq	$-8543223828751151131, %rdx
	movq	%rcx, %rax
	imulq	%rdx
	leaq	(%rdx,%rcx), %rax
	sarq	$29, %rax
	movq	%rcx, %rdx
	sarq	$63, %rdx
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rcx, %rax
	subq	%rdx, %rax
	movq	%rax, -8(%rbp)
	cmpq	$0, -8(%rbp)
	jns	.L2
	movq	-8(%rbp), %rax
	addq	$1000000007, %rax
	jmp	.L4
.L2:
	movq	-8(%rbp), %rax
.L4:
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE6:
	.size	MOD, .-MOD
	.globl	power
	.type	power, @function
power:
.LFB7:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%rbx
	subq	$24, %rsp
	.cfi_offset 3, -24
	movq	%rdi, -24(%rbp)
	movq	%rsi, -32(%rbp)
	cmpq	$0, -32(%rbp)
	jne	.L6
	movl	$1, %eax
	jmp	.L7
.L6:
	movq	-32(%rbp), %rax
	andl	$1, %eax
	testq	%rax, %rax
	jne	.L8
	movq	-32(%rbp), %rax
	movq	%rax, %rdx
	shrq	$63, %rdx
	addq	%rdx, %rax
	sarq	%rax
	movq	%rax, %rbx
	movq	-24(%rbp), %rax
	imulq	%rax, %rax
	movq	%rax, %rdi
	call	MOD
	movq	%rbx, %rsi
	movq	%rax, %rdi
	call	power
	jmp	.L7
.L8:
	movq	-32(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-24(%rbp), %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	power
	imulq	-24(%rbp), %rax
	movq	%rax, %rdi
	call	MOD
.L7:
	movq	-8(%rbp), %rbx
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE7:
	.size	power, .-power
	.globl	inverse
	.type	inverse, @function
inverse:
.LFB8:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$16, %rsp
	movq	%rdi, -8(%rbp)
	movq	-8(%rbp), %rax
	movl	$1000000005, %esi
	movq	%rax, %rdi
	call	power
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE8:
	.size	inverse, .-inverse
	.globl	fact
	.bss
	.align 8
	.type	fact, @object
	.size	fact, 8
fact:
	.zero	8
	.globl	fact_inv
	.align 8
	.type	fact_inv, @object
	.size	fact_inv, 8
fact_inv:
	.zero	8
	.text
	.globl	comb
	.type	comb, @function
comb:
.LFB9:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%rbx
	subq	$16, %rsp
	.cfi_offset 3, -24
	movq	%rdi, -16(%rbp)
	movq	%rsi, -24(%rbp)
	cmpq	$0, -24(%rbp)
	js	.L12
	movq	-16(%rbp), %rax
	cmpq	-24(%rbp), %rax
	jl	.L12
	cmpq	$0, -16(%rbp)
	jns	.L13
.L12:
	movl	$0, %eax
	jmp	.L14
.L13:
	movq	fact(%rip), %rdx
	movq	-16(%rbp), %rax
	salq	$3, %rax
	addq	%rdx, %rax
	movq	(%rax), %rbx
	movq	fact_inv(%rip), %rdx
	movq	-24(%rbp), %rax
	salq	$3, %rax
	addq	%rdx, %rax
	movq	(%rax), %rdx
	movq	fact_inv(%rip), %rcx
	movq	-16(%rbp), %rax
	subq	-24(%rbp), %rax
	salq	$3, %rax
	addq	%rcx, %rax
	movq	(%rax), %rax
	imulq	%rdx, %rax
	movq	%rax, %rdi
	call	MOD
	imulq	%rbx, %rax
	movq	%rax, %rdi
	call	MOD
.L14:
	movq	-8(%rbp), %rbx
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE9:
	.size	comb, .-comb
	.section	.rodata
.LC0:
	.string	"%lld%lld"
.LC1:
	.string	"%lld\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB10:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%r12
	pushq	%rbx
	subq	$64, %rsp
	.cfi_offset 12, -24
	.cfi_offset 3, -32
	movq	%fs:40, %rax
	movq	%rax, -24(%rbp)
	xorl	%eax, %eax
	leaq	-64(%rbp), %rdx
	leaq	-72(%rbp), %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, fact(%rip)
	movq	fact(%rip), %rax
	movq	$1, (%rax)
	movq	$1, -56(%rbp)
	jmp	.L16
.L17:
	movq	fact(%rip), %rdx
	movq	-56(%rbp), %rax
	salq	$3, %rax
	subq	$8, %rax
	addq	%rdx, %rax
	movq	(%rax), %rax
	imulq	-56(%rbp), %rax
	movq	fact(%rip), %rcx
	movq	-56(%rbp), %rdx
	salq	$3, %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	MOD
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L16:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jle	.L17
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, fact_inv(%rip)
	movq	$0, -56(%rbp)
	jmp	.L18
.L19:
	movq	fact(%rip), %rdx
	movq	-56(%rbp), %rax
	salq	$3, %rax
	addq	%rdx, %rax
	movq	(%rax), %rax
	movq	fact_inv(%rip), %rcx
	movq	-56(%rbp), %rdx
	salq	$3, %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	inverse
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L18:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jle	.L19
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, -48(%rbp)
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, -40(%rbp)
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, -32(%rbp)
	movq	$0, -56(%rbp)
	jmp	.L20
.L21:
	movq	-56(%rbp), %rax
	leaq	0(,%rax,8), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	$0, (%rax)
	addq	$1, -56(%rbp)
.L20:
	movq	-64(%rbp), %rax
	cmpq	%rax, -56(%rbp)
	jl	.L21
	movq	-64(%rbp), %rax
	movq	%rax, -56(%rbp)
	jmp	.L22
.L23:
	movq	-56(%rbp), %rax
	salq	$3, %rax
	leaq	-8(%rax), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	(%rax), %r12
	movq	-64(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-56(%rbp), %rax
	subq	$1, %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	comb
	movq	%rax, %rbx
	movq	-56(%rbp), %rax
	movq	%rax, %rsi
	movl	$2, %edi
	call	power
	movq	%rax, %rdi
	call	inverse
	imulq	%rbx, %rax
	addq	%r12, %rax
	movq	-56(%rbp), %rdx
	leaq	0(,%rdx,8), %rcx
	movq	-48(%rbp), %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	MOD
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L22:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jl	.L23
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	$1, (%rax)
	movq	$0, -56(%rbp)
	jmp	.L24
.L25:
	movq	-56(%rbp), %rax
	leaq	0(,%rax,8), %rdx
	movq	-40(%rbp), %rax
	addq	%rdx, %rax
	movq	$0, (%rax)
	addq	$1, -56(%rbp)
.L24:
	movq	-72(%rbp), %rax
	cmpq	%rax, -56(%rbp)
	jl	.L25
	movq	-72(%rbp), %rax
	movq	%rax, -56(%rbp)
	jmp	.L26
.L27:
	movq	-56(%rbp), %rax
	salq	$3, %rax
	leaq	-8(%rax), %rdx
	movq	-40(%rbp), %rax
	addq	%rdx, %rax
	movq	(%rax), %r12
	movq	-72(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-56(%rbp), %rax
	subq	$1, %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	comb
	movq	%rax, %rbx
	movq	-56(%rbp), %rax
	movq	%rax, %rsi
	movl	$2, %edi
	call	power
	movq	%rax, %rdi
	call	inverse
	imulq	%rbx, %rax
	addq	%r12, %rax
	movq	-56(%rbp), %rdx
	leaq	0(,%rdx,8), %rcx
	movq	-40(%rbp), %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	MOD
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L26:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jl	.L27
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	movq	-40(%rbp), %rax
	addq	%rdx, %rax
	movq	$1, (%rax)
	movq	$0, -56(%rbp)
	jmp	.L28
.L29:
	movq	-56(%rbp), %rax
	leaq	0(,%rax,8), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	(%rax), %rax
	movl	$1, %edx
	subq	%rax, %rdx
	movq	-56(%rbp), %rax
	leaq	0(,%rax,8), %rcx
	movq	-40(%rbp), %rax
	addq	%rcx, %rax
	movq	(%rax), %rcx
	movq	%rdx, %rax
	subq	%rcx, %rax
	movq	-56(%rbp), %rdx
	leaq	0(,%rdx,8), %rcx
	movq	-32(%rbp), %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	MOD
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L28:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jl	.L29
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	movq	-32(%rbp), %rax
	addq	%rdx, %rax
	movq	$0, (%rax)
	movq	$1, -56(%rbp)
	jmp	.L30
.L31:
	movq	-56(%rbp), %rax
	salq	$3, %rax
	leaq	-8(%rax), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	(%rax), %rbx
	movl	$2, %edi
	call	inverse
	movq	-56(%rbp), %rdx
	salq	$3, %rdx
	leaq	-8(%rdx), %rcx
	movq	-32(%rbp), %rdx
	addq	%rcx, %rdx
	movq	(%rdx), %rdx
	imulq	%rdx, %rax
	addq	%rbx, %rax
	movq	%rax, %rdi
	call	MOD
	movq	%rax, %rsi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	addq	$1, -56(%rbp)
.L30:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jle	.L31
	movl	$0, %eax
	movq	-24(%rbp), %rdx
	subq	%fs:40, %rdx
	je	.L33
	call	__stack_chk_fail@PLT
.L33:
	addq	$64, %rsp
	popq	%rbx
	popq	%r12
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE10:
	.size	main, .-main
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:
```

Only output the optimized assembly code. Do not include any other text. Do not write any comments in the assembly code. Wrap the assembly code in ```assembly``` tags.
user
	.file	"temp.c"
	.text
	.p2align 4
	.globl	MOD
	.type	MOD, @function
MOD:
.LFB39:
	.cfi_startproc
	endbr64
	movabsq	$-8543223828751151131, %rdx
	movq	%rdi, %rax
	imulq	%rdx
	leaq	(%rdx,%rdi), %rax
	movq	%rdi, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rdi, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	ret
	.cfi_endproc
.LFE39:
	.size	MOD, .-MOD
	.p2align 4
	.globl	power
	.type	power, @function
power:
.LFB40:
	.cfi_startproc
	endbr64
	testq	%rsi, %rsi
	je	.L32
	pushq	%r12
	.cfi_def_cfa_offset 16
	.cfi_offset 12, -16
	pushq	%rbp
	.cfi_def_cfa_offset 24
	.cfi_offset 6, -24
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -32
	movq	%rdi, %rbx
	movabsq	$-8543223828751151131, %rdi
	subq	$16, %rsp
	.cfi_def_cfa_offset 48
	testb	$1, %sil
	je	.L6
	jmp	.L71
	.p2align 4,,10
	.p2align 3
.L58:
	testb	$1, %sil
	jne	.L8
.L6:
	imulq	%rbx, %rbx
	movq	%rsi, %rax
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rbx, %rax
	movq	%rbx, %rcx
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	sarq	%rsi
	movq	%rcx, %rbx
	jne	.L58
	movl	$1, %eax
.L4:
	addq	$16, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 32
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%rbp
	.cfi_def_cfa_offset 16
	popq	%r12
	.cfi_def_cfa_offset 8
	ret
	.p2align 4,,10
	.p2align 3
.L8:
	.cfi_restore_state
	subq	$1, %rsi
	je	.L72
.L31:
	movabsq	$-8543223828751151131, %rdi
	movq	%rbx, %rbp
	testb	$1, %sil
	je	.L11
	jmp	.L73
	.p2align 4,,10
	.p2align 3
.L60:
	testb	$1, %sil
	jne	.L13
.L11:
	movq	%rbp, %rcx
	movq	%rsi, %rax
	imulq	%rbp, %rcx
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rcx, %rax
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	sarq	%rsi
	movq	%rcx, %rbp
	jne	.L60
.L10:
	movabsq	$-8543223828751151131, %rdx
	movq	%rbx, %rax
	imulq	%rdx
	leaq	(%rdx,%rbx), %rax
	movq	%rbx, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rbx, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	addq	$16, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 32
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%rbp
	.cfi_def_cfa_offset 16
	popq	%r12
	.cfi_def_cfa_offset 8
	ret
	.p2align 4,,10
	.p2align 3
.L13:
	.cfi_restore_state
	subq	$1, %rsi
	je	.L74
.L30:
	movabsq	$-8543223828751151131, %rdi
	movq	%rbp, %r12
	testb	$1, %sil
	je	.L16
	jmp	.L75
	.p2align 4,,10
	.p2align 3
.L62:
	testb	$1, %sil
	jne	.L18
.L16:
	movq	%r12, %rcx
	movq	%rsi, %rax
	imulq	%r12, %rcx
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rcx, %rax
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	sarq	%rsi
	movq	%rcx, %r12
	jne	.L62
.L15:
	movabsq	$-8543223828751151131, %rdx
	movq	%rbp, %rax
	imulq	%rdx
	leaq	(%rdx,%rbp), %rax
	movq	%rbp, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rbp, %rax
	subq	%rdx, %rax
	js	.L26
.L70:
	imulq	%rax, %rbx
	jmp	.L10
	.p2align 4,,10
	.p2align 3
.L26:
	addq	$1000000007, %rax
	jmp	.L70
	.p2align 4,,10
	.p2align 3
.L18:
	subq	$1, %rsi
	je	.L76
.L28:
	movabsq	$-8543223828751151131, %rdi
	movq	%r12, %rdx
	testb	$1, %sil
	je	.L21
	jmp	.L22
	.p2align 4,,10
	.p2align 3
.L63:
	testb	$1, %sil
	jne	.L22
.L21:
	imulq	%rdx, %rdx
	movq	%rsi, %rax
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rdx, %rax
	movq	%rdx, %rcx
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	movq	%rcx, %rdx
	subq	%rax, %rdx
	sarq	%rsi
	jne	.L63
.L20:
	movabsq	$-8543223828751151131, %rdx
	movq	%r12, %rax
	imulq	%rdx
	leaq	(%rdx,%r12), %rax
	movq	%r12, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%r12, %rax
	subq	%rdx, %rax
	jns	.L69
	addq	$1000000007, %rax
.L69:
	imulq	%rax, %rbp
	jmp	.L15
.L22:
	movq	%rdx, %rdi
	subq	$1, %rsi
	movq	%rdx, 8(%rsp)
	call	power
	movq	8(%rsp), %rdx
	imulq	%rdx, %rax
	movabsq	$-8543223828751151131, %rdx
	movq	%rax, %rcx
	imulq	%rdx
	leaq	(%rdx,%rcx), %rax
	movq	%rcx, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rcx, %rax
	subq	%rdx, %rax
	js	.L24
.L68:
	imulq	%rax, %r12
	jmp	.L20
.L32:
	.cfi_def_cfa_offset 8
	.cfi_restore 3
	.cfi_restore 6
	.cfi_restore 12
	movl	$1, %eax
	ret
.L71:
	.cfi_def_cfa_offset 48
	.cfi_offset 3, -32
	.cfi_offset 6, -24
	.cfi_offset 12, -16
	subq	$1, %rsi
	jne	.L31
	jmp	.L10
.L24:
	addq	$1000000007, %rax
	jmp	.L68
.L74:
	imulq	%rbp, %rbx
	jmp	.L10
.L73:
	subq	$1, %rsi
	jne	.L30
	jmp	.L15
	.p2align 4,,10
	.p2align 3
.L72:
	movq	%rbx, %rax
	jmp	.L4
.L75:
	subq	$1, %rsi
	jne	.L28
	jmp	.L20
.L76:
	imulq	%r12, %rbp
	jmp	.L15
	.cfi_endproc
.LFE40:
	.size	power, .-power
	.p2align 4
	.globl	inverse
	.type	inverse, @function
inverse:
.LFB41:
	.cfi_startproc
	endbr64
	movq	%rdi, %rcx
	movq	%rdi, %r10
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	imulq	%rdi, %rcx
	movabsq	$-8543223828751151131, %rdi
	movq	%rcx, %rax
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	imulq	%rcx, %rcx
	movq	%rcx, %rax
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movq	%rcx, %r9
	movq	%rcx, %r8
	movl	$250000000, %ecx
	jmp	.L78
	.p2align 4,,10
	.p2align 3
.L98:
	testb	$1, %cl
	jne	.L79
.L78:
	movq	%r8, %rsi
	movq	%rcx, %rax
	imulq	%r8, %rsi
	shrq	$63, %rax
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	sarq	%rcx
	movq	%rsi, %r8
	jne	.L98
.L80:
	movabsq	$-8543223828751151131, %rdx
	imulq	%r10, %r9
	movq	%r9, %rax
	imulq	%rdx
	leaq	(%rdx,%r9), %rax
	movq	%r9, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%r9, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	addq	$24, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 8
	ret
	.p2align 4,,10
	.p2align 3
.L79:
	.cfi_restore_state
	subq	$1, %rcx
	je	.L105
	movabsq	$-8543223828751151131, %rdi
	movq	%r8, %rdx
	testb	$1, %cl
	je	.L82
	jmp	.L83
	.p2align 4,,10
	.p2align 3
.L99:
	testb	$1, %cl
	jne	.L83
.L82:
	movq	%rdx, %rsi
	movq	%rcx, %rax
	imulq	%rdx, %rsi
	shrq	$63, %rax
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	sarq	%rcx
	movq	%rsi, %rdx
	jne	.L99
.L84:
	movabsq	$-8543223828751151131, %rdx
	imulq	%r9, %r8
	movq	%r8, %rax
	mulq	%rdx
.L104:
	shrq	$29, %rdx
	movq	%r8, %r9
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %r9
	jmp	.L80
.L83:
	leaq	-1(%rcx), %rsi
	movq	%rdx, %rdi
	movq	%rdx, 8(%rsp)
	call	power
	movq	8(%rsp), %rdx
	movabsq	$-8543223828751151131, %rsi
	imulq	%rax, %rdx
	movq	%rdx, %rax
	movq	%rdx, %rcx
	imulq	%rsi
	leaq	(%rdx,%rcx), %rax
	movq	%rcx, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rcx, %rax
	subq	%rdx, %rax
	js	.L86
	movq	%r8, %rcx
	imulq	%rax, %rcx
.L103:
	movq	%rcx, %rax
	mulq	%rsi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movq	%rcx, %r8
	jmp	.L84
.L86:
	leaq	1000000007(%rax), %rcx
	imulq	%r8, %rcx
	jmp	.L103
.L105:
	imulq	%r9, %r8
	movq	%r8, %rax
	mulq	%rdi
	jmp	.L104
	.cfi_endproc
.LFE41:
	.size	inverse, .-inverse
	.p2align 4
	.globl	comb
	.type	comb, @function
comb:
.LFB42:
	.cfi_startproc
	endbr64
	testq	%rsi, %rsi
	js	.L109
	cmpq	%rdi, %rsi
	jg	.L109
	movq	fact_inv(%rip), %rdx
	movq	%rdi, %rax
	movabsq	$-8543223828751151131, %rcx
	subq	%rsi, %rax
	movq	(%rdx,%rax,8), %rax
	imulq	(%rdx,%rsi,8), %rax
	movq	%rax, %rsi
	imulq	%rcx
	leaq	(%rdx,%rsi), %rax
	movq	%rsi, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rsi, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	movq	fact(%rip), %rdx
	imulq	(%rdx,%rdi,8), %rax
	movq	%rax, %rsi
	imulq	%rcx
	leaq	(%rdx,%rsi), %rax
	movq	%rsi, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rsi, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	ret
	.p2align 4,,10
	.p2align 3
.L109:
	xorl	%eax, %eax
	ret
	.cfi_endproc
.LFE42:
	.size	comb, .-comb
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"%lld%lld"
.LC1:
	.string	"%lld\n"
	.section	.text.startup,"ax",@progbits
	.p2align 4
	.globl	main
	.type	main, @function
main:
.LFB43:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	leaq	.LC0(%rip), %rdi
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	subq	$104, %rsp
	.cfi_def_cfa_offset 160
	movq	%fs:40, %rax
	movq	%rax, 88(%rsp)
	xorl	%eax, %eax
	leaq	80(%rsp), %rdx
	leaq	72(%rsp), %rsi
	call	__isoc99_scanf@PLT
	movq	72(%rsp), %rbx
	movq	80(%rsp), %rbp
	leaq	(%rbx,%rbp), %r12
	leaq	8(,%r12,8), %r15
	movq	%r15, %rdi
	call	malloc@PLT
	movq	%rax, (%rsp)
	movq	%rax, fact(%rip)
	movq	$1, (%rax)
	testq	%r12, %r12
	jle	.L341
	movq	$1, 8(%rax)
	movq	(%rsp), %r8
	movl	$1, %eax
	movl	$2, %ecx
	movabsq	$-8543223828751151131, %rdi
	cmpq	$1, %r12
	jne	.L114
	jmp	.L115
	.p2align 4,,10
	.p2align 3
.L213:
	movq	%rdx, %rcx
.L114:
	imulq	%rcx, %rax
	movq	%rax, %rsi
	imulq	%rdi
	leaq	(%rdx,%rsi), %rax
	movq	%rsi, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rsi, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	leaq	1(%rcx), %rdx
	movq	%rax, (%r8,%rcx,8)
	cmpq	%rcx, %r12
	jne	.L213
.L115:
	movq	%r15, %rdi
	call	malloc@PLT
	movq	%rax, 16(%rsp)
	movq	%rax, fact_inv(%rip)
.L211:
	movq	%rbp, 8(%rsp)
	movq	%rbx, %rbp
	xorl	%r13d, %r13d
	movq	(%rsp), %r14
	movabsq	$-8543223828751151131, %r11
	movq	16(%rsp), %rbx
.L126:
	movq	(%r14,%r13,8), %r10
	movq	%r10, %rsi
	imulq	%r10, %rsi
	movq	%rsi, %rax
	mulq	%r11
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	imulq	%rsi, %rsi
	movq	%rsi, %rax
	mulq	%r11
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movl	$250000000, %eax
	movq	%rsi, %r9
	movq	%rsi, %r8
	jmp	.L117
	.p2align 4,,10
	.p2align 3
.L298:
	testb	$1, %al
	jne	.L118
.L117:
	movq	%r8, %rdi
	movq	%rax, %rdx
	imulq	%r8, %rdi
	shrq	$63, %rdx
	leaq	(%rdx,%rax), %rsi
	movq	%rdi, %rax
	mulq	%r11
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rdi
	movq	%rsi, %rax
	sarq	%rax
	movq	%rdi, %r8
	jne	.L298
.L119:
	imulq	%r9, %r10
	movq	%r10, %rax
	imulq	%r11
	movq	%r10, %rax
	sarq	$63, %rax
	addq	%r10, %rdx
	sarq	$29, %rdx
	subq	%rax, %rdx
	imulq	$1000000007, %rdx, %rax
	movq	%r10, %rdx
	subq	%rax, %rdx
	leaq	1000000007(%rdx), %rax
	cmovs	%rax, %rdx
	movq	%rdx, (%rbx,%r13,8)
	addq	$1, %r13
	cmpq	%r13, %r12
	jge	.L126
	movq	%rbp, %rbx
	movq	8(%rsp), %rbp
.L116:
	movq	%r15, %rdi
	call	malloc@PLT
	movq	%r15, %rdi
	movq	%rax, %r13
	call	malloc@PLT
	movq	%r15, %rdi
	movq	%rax, %r14
	call	malloc@PLT
	movq	%rax, 24(%rsp)
	testq	%rbp, %rbp
	jle	.L130
	leaq	0(,%rbp,8), %rdx
	xorl	%esi, %esi
	movq	%r13, %rdi
	call	memset@PLT
.L130:
	cmpq	%r12, %rbp
	jge	.L129
	movq	16(%rsp), %rdi
	leaq	-1(%rbp), %rax
	movq	%rbp, %rdx
	movq	%r14, 32(%rsp)
	movq	%rax, %rsi
	negq	%rdx
	movq	%rbx, 40(%rsp)
	movabsq	$-8543223828751151131, %r10
	leaq	(%rdi,%rax,8), %r15
	shrq	$63, %rsi
	leaq	(%rdi,%rdx,8), %rdi
	movq	-8(%r13,%rbp,8), %rbx
	movq	%rdi, 8(%rsp)
	movl	%esi, %r14d
	testq	%rax, %rax
	js	.L216
	.p2align 4,,10
	.p2align 3
.L343:
	testb	%r14b, %r14b
	jne	.L216
	movq	8(%rsp), %rax
	movq	(%r15), %rcx
	movq	(%rsp), %rdi
	imulq	(%rax,%rbp,8), %rcx
	movq	%rcx, %rax
	imulq	%r10
	leaq	(%rdx,%rcx), %rax
	movq	%rcx, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rcx, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	imulq	-8(%rdi,%rbp,8), %rax
	movq	%rax, %rcx
	imulq	%r10
	movq	%rcx, %rax
	sarq	$63, %rax
	leaq	(%rdx,%rcx), %r11
	sarq	$29, %r11
	subq	%rax, %r11
	imulq	$1000000007, %r11, %rax
	subq	%rax, %rcx
	movq	%rcx, %r11
	leaq	1000000007(%rcx), %rax
	cmovs	%rax, %r11
.L133:
	testq	%rbp, %rbp
	je	.L219
	movl	$2, %r8d
	movq	%rbp, %rax
	movq	%r8, %rdx
	testb	$1, %bpl
	je	.L136
	jmp	.L137
	.p2align 4,,10
	.p2align 3
.L300:
	testb	$1, %al
	jne	.L319
.L136:
	movq	%rdx, %rsi
	movq	%rax, %rcx
	imulq	%rdx, %rsi
	shrq	$63, %rcx
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movq	%rcx, %rax
	sarq	%rax
	movq	%rsi, %rdx
	jne	.L300
.L219:
	movl	$1, %r8d
.L135:
	movq	%r8, %rcx
	imulq	%r8, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	imulq	%rcx, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movl	$250000000, %eax
	movq	%rcx, %r9
	jmp	.L151
	.p2align 4,,10
	.p2align 3
.L304:
	testb	$1, %al
	jne	.L152
.L151:
	movq	%rcx, %rdi
	movq	%rax, %rdx
	imulq	%rcx, %rdi
	shrq	$63, %rdx
	leaq	(%rdx,%rax), %rsi
	movq	%rdi, %rax
	mulq	%r10
	movq	%rdx, %rcx
	shrq	$29, %rcx
	imulq	$1000000007, %rcx, %rax
	subq	%rax, %rdi
	movq	%rsi, %rax
	sarq	%rax
	movq	%rdi, %rcx
	jne	.L304
.L153:
	movq	%r8, %rcx
	imulq	%r9, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rdx
	subq	%rdx, %rcx
	imulq	%r11, %rcx
	addq	%rbx, %rcx
	movq	%rcx, %rax
	imulq	%r10
	movq	%rcx, %rax
	sarq	$63, %rax
	addq	%rcx, %rdx
	sarq	$29, %rdx
	subq	%rax, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movq	%rcx, %rdx
	leaq	1000000007(%rcx), %rax
	cmovs	%rax, %rdx
	movq	%rdx, 0(%r13,%rbp,8)
	addq	$1, %rbp
	cmpq	%rbp, %r12
	je	.L342
	leaq	-1(%rbp), %rax
	movq	-8(%r13,%rbp,8), %rbx
	testq	%rax, %rax
	jns	.L343
.L216:
	xorl	%r11d, %r11d
	jmp	.L133
	.p2align 4,,10
	.p2align 3
.L118:
	subq	$1, %rax
	movq	%rax, %rsi
	je	.L344
	movq	%r8, %rdx
	testb	$1, %sil
	je	.L121
	jmp	.L122
	.p2align 4,,10
	.p2align 3
.L299:
	testb	$1, %sil
	jne	.L122
.L121:
	movq	%rdx, %rdi
	movq	%rsi, %rax
	imulq	%rdx, %rdi
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rdi, %rax
	mulq	%r11
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rdi
	sarq	%rsi
	movq	%rdi, %rdx
	jne	.L299
	movl	$1, %esi
.L123:
	imulq	%r8, %rsi
	movq	%rsi, %rax
	mulq	%r11
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	imulq	%r9, %rsi
	movq	%rsi, %rax
	mulq	%r11
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movq	%rsi, %r9
	jmp	.L119
	.p2align 4,,10
	.p2align 3
.L319:
	movq	%rdx, %r8
.L137:
	subq	$1, %rax
	je	.L135
	movq	%r8, %r9
	movq	%r8, %rdx
	testb	$1, %al
	jne	.L141
	.p2align 4,,10
	.p2align 3
.L140:
	movq	%rdx, %rsi
	movq	%rax, %rcx
	imulq	%rdx, %rsi
	shrq	$63, %rcx
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movq	%rcx, %rax
	sarq	%rax
	movq	%rsi, %rdx
	je	.L135
	testb	$1, %al
	je	.L140
	movq	%rdx, %r9
.L141:
	subq	$1, %rax
	je	.L143
	movq	%r9, %rcx
	movq	%r9, %rdx
	testb	$1, %al
	je	.L144
	jmp	.L145
	.p2align 4,,10
	.p2align 3
.L302:
	testb	$1, %al
	jne	.L323
.L144:
	movq	%rdx, %rsi
	movq	%rax, %rcx
	imulq	%rdx, %rsi
	shrq	$63, %rcx
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movq	%rcx, %rax
	sarq	%rax
	movq	%rsi, %rdx
	jne	.L302
.L143:
	imulq	%r8, %r9
	movq	%r9, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %r9
	movq	%r9, %r8
	jmp	.L135
	.p2align 4,,10
	.p2align 3
.L342:
	movq	32(%rsp), %r14
	movq	40(%rsp), %rbx
.L129:
	movq	$1, 0(%r13,%r12,8)
	testq	%rbx, %rbx
	jle	.L132
	leaq	0(,%rbx,8), %rdx
	xorl	%esi, %esi
	movq	%r14, %rdi
	call	memset@PLT
.L132:
	cmpq	%r12, %rbx
	jge	.L161
	movq	16(%rsp), %rdi
	leaq	-1(%rbx), %rax
	movq	%rbx, %rdx
	movq	%r13, 16(%rsp)
	movq	%rax, %rsi
	negq	%rdx
	movq	-8(%r14,%rbx,8), %rbp
	movabsq	$-8543223828751151131, %r10
	leaq	(%rdi,%rax,8), %rcx
	shrq	$63, %rsi
	leaq	(%rdi,%rdx,8), %rdi
	movq	%rdi, 8(%rsp)
	movq	%rcx, %r15
	movl	%esi, %r13d
	testq	%rax, %rax
	js	.L229
	.p2align 4,,10
	.p2align 3
.L346:
	testb	%r13b, %r13b
	jne	.L229
	movq	8(%rsp), %rax
	movq	(%r15), %rcx
	movq	(%rsp), %rdi
	imulq	(%rax,%rbx,8), %rcx
	movq	%rcx, %rax
	imulq	%r10
	leaq	(%rdx,%rcx), %rax
	movq	%rcx, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rcx, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	imulq	-8(%rdi,%rbx,8), %rax
	movq	%rax, %rcx
	imulq	%r10
	movq	%rcx, %rax
	sarq	$63, %rax
	leaq	(%rdx,%rcx), %r11
	sarq	$29, %r11
	subq	%rax, %r11
	imulq	$1000000007, %r11, %rax
	subq	%rax, %rcx
	movq	%rcx, %r11
	leaq	1000000007(%rcx), %rax
	cmovs	%rax, %r11
.L164:
	testq	%rbx, %rbx
	je	.L232
	movl	$2, %r8d
	movq	%rbx, %rax
	movq	%r8, %rdx
	testb	$1, %bl
	je	.L167
	jmp	.L168
	.p2align 4,,10
	.p2align 3
.L306:
	testb	$1, %al
	jne	.L330
.L167:
	movq	%rdx, %rsi
	movq	%rax, %rcx
	imulq	%rdx, %rsi
	shrq	$63, %rcx
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movq	%rcx, %rax
	sarq	%rax
	movq	%rsi, %rdx
	jne	.L306
.L232:
	movl	$1, %r8d
.L166:
	movq	%r8, %rcx
	imulq	%r8, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	imulq	%rcx, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movl	$250000000, %eax
	movq	%rcx, %r9
	jmp	.L182
	.p2align 4,,10
	.p2align 3
.L310:
	testb	$1, %al
	jne	.L183
.L182:
	movq	%rcx, %rdi
	movq	%rax, %rdx
	imulq	%rcx, %rdi
	shrq	$63, %rdx
	leaq	(%rdx,%rax), %rsi
	movq	%rdi, %rax
	mulq	%r10
	movq	%rdx, %rcx
	shrq	$29, %rcx
	imulq	$1000000007, %rcx, %rax
	subq	%rax, %rdi
	movq	%rsi, %rax
	sarq	%rax
	movq	%rdi, %rcx
	jne	.L310
.L184:
	movq	%r8, %rcx
	imulq	%r9, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rdx
	subq	%rdx, %rcx
	imulq	%r11, %rcx
	addq	%rbp, %rcx
	movq	%rcx, %rax
	imulq	%r10
	movq	%rcx, %rax
	sarq	$63, %rax
	addq	%rcx, %rdx
	sarq	$29, %rdx
	subq	%rax, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movq	%rcx, %rdx
	leaq	1000000007(%rcx), %rax
	cmovs	%rax, %rdx
	movq	%rdx, (%r14,%rbx,8)
	addq	$1, %rbx
	cmpq	%rbx, %r12
	je	.L345
	leaq	-1(%rbx), %rax
	movq	-8(%r14,%rbx,8), %rbp
	testq	%rax, %rax
	jns	.L346
.L229:
	xorl	%r11d, %r11d
	jmp	.L164
	.p2align 4,,10
	.p2align 3
.L330:
	movq	%rdx, %r8
.L168:
	subq	$1, %rax
	je	.L166
	movq	%r8, %r9
	movq	%r8, %rdx
	testb	$1, %al
	jne	.L172
	.p2align 4,,10
	.p2align 3
.L171:
	movq	%rdx, %rsi
	movq	%rax, %rcx
	imulq	%rdx, %rsi
	shrq	$63, %rcx
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movq	%rcx, %rax
	sarq	%rax
	movq	%rsi, %rdx
	je	.L166
	testb	$1, %al
	je	.L171
	movq	%rdx, %r9
.L172:
	subq	$1, %rax
	je	.L174
	movq	%r9, %rcx
	movq	%r9, %rdx
	testb	$1, %al
	je	.L175
	jmp	.L176
	.p2align 4,,10
	.p2align 3
.L308:
	testb	$1, %al
	jne	.L334
.L175:
	movq	%rdx, %rsi
	movq	%rax, %rcx
	imulq	%rdx, %rsi
	shrq	$63, %rcx
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movq	%rcx, %rax
	sarq	%rax
	movq	%rsi, %rdx
	jne	.L308
.L174:
	imulq	%r8, %r9
	movq	%r9, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %r9
	movq	%r9, %r8
	jmp	.L166
	.p2align 4,,10
	.p2align 3
.L345:
	movq	16(%rsp), %r13
.L161:
	movq	$1, (%r14,%r12,8)
	movq	24(%rsp), %r9
	xorl	%esi, %esi
	movl	$1, %r8d
	movabsq	$-8543223828751151131, %rdi
	testq	%r12, %r12
	jle	.L163
	.p2align 4,,10
	.p2align 3
.L162:
	movq	%r8, %rcx
	subq	0(%r13,%rsi,8), %rcx
	subq	(%r14,%rsi,8), %rcx
	movq	%rcx, %rax
	imulq	%rdi
	movq	%rcx, %rax
	sarq	$63, %rax
	addq	%rcx, %rdx
	sarq	$29, %rdx
	subq	%rax, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movq	%rcx, %rdx
	leaq	1000000007(%rcx), %rax
	cmovs	%rax, %rdx
	movq	%rdx, (%r9,%rsi,8)
	addq	$1, %rsi
	cmpq	%rsi, %r12
	jne	.L162
	movq	24(%rsp), %r14
	leaq	.LC1(%rip), %rbx
	movabsq	$-8543223828751151131, %rbp
	movq	$0, (%r14,%r12,8)
	movl	$1, %r12d
	.p2align 4,,10
	.p2align 3
.L202:
	movq	-8(%r13,%r12,8), %r9
	movl	$16, %r8d
	movl	$250000000, %ecx
	jmp	.L193
	.p2align 4,,10
	.p2align 3
.L314:
	testb	$1, %cl
	jne	.L194
.L193:
	movq	%r8, %rsi
	movq	%rcx, %rax
	imulq	%r8, %rsi
	shrq	$63, %rax
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%rbp
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	sarq	%rcx
	movq	%rsi, %r8
	jne	.L314
	movl	$16, %ecx
.L195:
	addq	%rcx, %rcx
	movq	%rbx, %rsi
	movl	$1, %edi
	movq	%rcx, %rax
	mulq	%rbp
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rdx
	subq	%rdx, %rcx
	imulq	-8(%r14,%r12,8), %rcx
	addq	%r9, %rcx
	movq	%rcx, %rax
	imulq	%rbp
	movq	%rcx, %rax
	sarq	$63, %rax
	addq	%rcx, %rdx
	sarq	$29, %rdx
	subq	%rax, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	leaq	1000000007(%rcx), %rax
	movq	%rcx, %rdx
	cmovs	%rax, %rdx
	xorl	%eax, %eax
	addq	$1, %r12
	call	__printf_chk@PLT
	movq	80(%rsp), %rax
	addq	72(%rsp), %rax
	cmpq	%r12, %rax
	jge	.L202
.L163:
	movq	88(%rsp), %rax
	subq	%fs:40, %rax
	jne	.L347
	addq	$104, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	xorl	%eax, %eax
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.p2align 4,,10
	.p2align 3
.L152:
	.cfi_restore_state
	subq	$1, %rax
	movq	%rax, %rsi
	je	.L227
	movq	%rcx, %rdx
	testb	$1, %al
	je	.L156
	jmp	.L157
	.p2align 4,,10
	.p2align 3
.L305:
	testb	$1, %sil
	jne	.L157
.L156:
	movq	%rdx, %rdi
	movq	%rsi, %rax
	imulq	%rdx, %rdi
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rdi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rdi
	sarq	%rsi
	movq	%rdi, %rdx
	jne	.L305
.L227:
	movl	$1, %edx
.L155:
	movq	%rcx, %rax
	movl	$1000000007, %esi
	imulq	%rdx, %rax
	cqto
	idivq	%rsi
	movq	%rdx, %rax
	imulq	%r9, %rax
	cqto
	idivq	%rsi
	movq	%rdx, %r9
	jmp	.L153
	.p2align 4,,10
	.p2align 3
.L183:
	subq	$1, %rax
	movq	%rax, %rsi
	je	.L240
	movq	%rcx, %rdx
	testb	$1, %al
	je	.L187
	jmp	.L188
	.p2align 4,,10
	.p2align 3
.L311:
	testb	$1, %sil
	jne	.L188
.L187:
	movq	%rdx, %rdi
	movq	%rsi, %rax
	imulq	%rdx, %rdi
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rdi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rdi
	sarq	%rsi
	movq	%rdi, %rdx
	jne	.L311
.L240:
	movl	$1, %edx
.L186:
	movq	%rcx, %rax
	movl	$1000000007, %esi
	imulq	%rdx, %rax
	cqto
	idivq	%rsi
	movq	%rdx, %rax
	imulq	%r9, %rax
	cqto
	idivq	%rsi
	movq	%rdx, %r9
	jmp	.L184
	.p2align 4,,10
	.p2align 3
.L334:
	movq	%rdx, %rcx
.L176:
	subq	$1, %rax
	movq	%rax, %rsi
	je	.L237
	movq	%rcx, %rdx
	testb	$1, %al
	je	.L179
	jmp	.L180
	.p2align 4,,10
	.p2align 3
.L309:
	testb	$1, %sil
	jne	.L180
.L179:
	movq	%rdx, %rdi
	movq	%rsi, %rax
	imulq	%rdx, %rdi
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rdi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rdi
	sarq	%rsi
	movq	%rdi, %rdx
	jne	.L309
.L237:
	movl	$1, %edx
.L178:
	imulq	%rdx, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	imulq	%r9, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movq	%rcx, %r9
	jmp	.L174
	.p2align 4,,10
	.p2align 3
.L323:
	movq	%rdx, %rcx
.L145:
	subq	$1, %rax
	movq	%rax, %rsi
	je	.L224
	movq	%rcx, %rdx
	testb	$1, %al
	je	.L148
	jmp	.L149
	.p2align 4,,10
	.p2align 3
.L303:
	testb	$1, %sil
	jne	.L149
.L148:
	movq	%rdx, %rdi
	movq	%rsi, %rax
	imulq	%rdx, %rdi
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rdi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rdi
	sarq	%rsi
	movq	%rdi, %rdx
	jne	.L303
.L224:
	movl	$1, %edx
.L147:
	imulq	%rdx, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	imulq	%r9, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movq	%rcx, %r9
	jmp	.L143
	.p2align 4,,10
	.p2align 3
.L194:
	subq	$1, %rcx
	je	.L348
	movq	%r8, %rdx
	testb	$1, %cl
	je	.L197
	jmp	.L198
	.p2align 4,,10
	.p2align 3
.L315:
	testb	$1, %cl
	jne	.L198
.L197:
	movq	%rdx, %rsi
	movq	%rcx, %rax
	imulq	%rdx, %rsi
	shrq	$63, %rax
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%rbp
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	sarq	%rcx
	movq	%rsi, %rdx
	jne	.L315
	movl	$1, %esi
.L199:
	imulq	%r8, %rsi
	movq	%rsi, %rax
	mulq	%rbp
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	salq	$4, %rsi
	movq	%rsi, %rax
	mulq	%rbp
	movq	%rdx, %rcx
	shrq	$29, %rcx
	imulq	$1000000007, %rcx, %rax
	subq	%rax, %rsi
	movq	%rsi, %rcx
	jmp	.L195
.L180:
	subq	$1, %rsi
	movq	%rdx, %rdi
	movq	%rcx, 40(%rsp)
	movq	%rdx, 32(%rsp)
	call	power
	movq	32(%rsp), %rdx
	movl	$1000000007, %esi
	movq	40(%rsp), %rcx
	imulq	%rdx, %rax
	cqto
	idivq	%rsi
	testq	%rdx, %rdx
	jns	.L178
	addq	$1000000007, %rdx
	jmp	.L178
.L149:
	subq	$1, %rsi
	movq	%rdx, %rdi
	movq	%rcx, 56(%rsp)
	movq	%rdx, 48(%rsp)
	call	power
	movq	48(%rsp), %rdx
	movl	$1000000007, %esi
	movq	56(%rsp), %rcx
	imulq	%rdx, %rax
	cqto
	idivq	%rsi
	testq	%rdx, %rdx
	jns	.L147
	addq	$1000000007, %rdx
	jmp	.L147
.L198:
	movq	%rdx, %rdi
	leaq	-1(%rcx), %rsi
	movq	%rdx, (%rsp)
	call	power
	movq	(%rsp), %rdx
	movl	$1000000007, %edi
	imulq	%rdx, %rax
	cqto
	idivq	%rdi
	movq	%rdx, %rsi
	testq	%rdx, %rdx
	jns	.L199
	addq	$1000000007, %rsi
	jmp	.L199
.L157:
	subq	$1, %rsi
	movq	%rdx, %rdi
	movq	%rcx, 56(%rsp)
	movq	%rdx, 48(%rsp)
	call	power
	movq	48(%rsp), %rdx
	movl	$1000000007, %esi
	movq	56(%rsp), %rcx
	imulq	%rdx, %rax
	cqto
	idivq	%rsi
	testq	%rdx, %rdx
	jns	.L155
	addq	$1000000007, %rdx
	jmp	.L155
.L188:
	subq	$1, %rsi
	movq	%rdx, %rdi
	movq	%rcx, 40(%rsp)
	movq	%rdx, 32(%rsp)
	call	power
	movq	32(%rsp), %rdx
	movl	$1000000007, %esi
	movq	40(%rsp), %rcx
	imulq	%rdx, %rax
	cqto
	idivq	%rsi
	testq	%rdx, %rdx
	jns	.L186
	addq	$1000000007, %rdx
	jmp	.L186
.L122:
	movq	%rdx, %rdi
	subq	$1, %rsi
	movq	%rdx, 24(%rsp)
	call	power
	movq	24(%rsp), %rdx
	movl	$1000000007, %edi
	imulq	%rdx, %rax
	cqto
	idivq	%rdi
	movq	%rdx, %rsi
	testq	%rdx, %rdx
	jns	.L123
	addq	$1000000007, %rsi
	jmp	.L123
.L341:
	movq	%r15, %rdi
	call	malloc@PLT
	movq	%rax, 16(%rsp)
	movq	%rax, fact_inv(%rip)
	testq	%r12, %r12
	jne	.L116
	jmp	.L211
.L344:
	movq	%r9, %rax
	movl	$1000000007, %edi
	imulq	%r8, %rax
	cqto
	idivq	%rdi
	movq	%rdx, %r9
	jmp	.L119
.L348:
	movq	%r8, %rax
	movl	$1000000007, %edi
	salq	$4, %rax
	cqto
	idivq	%rdi
	movq	%rdx, %rcx
	jmp	.L195
.L347:
	call	__stack_chk_fail@PLT
	.cfi_endproc
.LFE43:
	.size	main, .-main
	.globl	fact_inv
	.bss
	.align 8
	.type	fact_inv, @object
	.size	fact_inv, 8
fact_inv:
	.zero	8
	.globl	fact
	.align 8
	.type	fact, @object
	.size	fact, 8
fact:
	.zero	8
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:

rule
	.file	"temp.c"
	.text
	.p2align 4
	.globl	MOD
	.type	MOD, @function
MOD:
.LFB39:
	.cfi_startproc
	endbr64
	movabsq	$-8543223828751151131, %rdx
	movq	%rdi, %rax
	imulq	%rdx
	leaq	(%rdx,%rdi), %rax
	movq	%rdi, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rdi, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	ret
	.cfi_endproc
.LFE39:
	.size	MOD, .-MOD
	.p2align 4
	.globl	power
	.type	power, @function
power:
.LFB40:
	.cfi_startproc
	endbr64
	testq	%rsi, %rsi
	je	.L32
	pushq	%r12
	.cfi_def_cfa_offset 16
	.cfi_offset 12, -16
	pushq	%rbp
	.cfi_def_cfa_offset 24
	.cfi_offset 6, -24
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -32
	movq	%rdi, %rbx
	movabsq	$-8543223828751151131, %rdi
	subq	$16, %rsp
	.cfi_def_cfa_offset 48
	testb	$1, %sil
	je	.L6
	jmp	.L71
	.p2align 4,,10
	.p2align 3
.L58:
	testb	$1, %sil
	jne	.L8
.L6:
	imulq	%rbx, %rbx
	movq	%rsi, %rax
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rbx, %rax
	movq	%rbx, %rcx
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	sarq	%rsi
	movq	%rcx, %rbx
	jne	.L58
	movl	$1, %eax
.L4:
	addq	$16, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 32
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%rbp
	.cfi_def_cfa_offset 16
	popq	%r12
	.cfi_def_cfa_offset 8
	ret
	.p2align 4,,10
	.p2align 3
.L8:
	.cfi_restore_state
	subq	$1, %rsi
	je	.L72
.L31:
	movabsq	$-8543223828751151131, %rdi
	movq	%rbx, %rbp
	testb	$1, %sil
	je	.L11
	jmp	.L73
	.p2align 4,,10
	.p2align 3
.L60:
	testb	$1, %sil
	jne	.L13
.L11:
	movq	%rbp, %rcx
	movq	%rsi, %rax
	imulq	%rbp, %rcx
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rcx, %rax
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	sarq	%rsi
	movq	%rcx, %rbp
	jne	.L60
.L10:
	movabsq	$-8543223828751151131, %rdx
	movq	%rbx, %rax
	imulq	%rdx
	leaq	(%rdx,%rbx), %rax
	movq	%rbx, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rbx, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	addq	$16, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 32
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%rbp
	.cfi_def_cfa_offset 16
	popq	%r12
	.cfi_def_cfa_offset 8
	ret
	.p2align 4,,10
	.p2align 3
.L13:
	.cfi_restore_state
	subq	$1, %rsi
	je	.L74
.L30:
	movabsq	$-8543223828751151131, %rdi
	movq	%rbp, %r12
	testb	$1, %sil
	je	.L16
	jmp	.L75
	.p2align 4,,10
	.p2align 3
.L62:
	testb	$1, %sil
	jne	.L18
.L16:
	movq	%r12, %rcx
	movq	%rsi, %rax
	imulq	%r12, %rcx
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rcx, %rax
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	sarq	%rsi
	movq	%rcx, %r12
	jne	.L62
.L15:
	movabsq	$-8543223828751151131, %rdx
	movq	%rbp, %rax
	imulq	%rdx
	leaq	(%rdx,%rbp), %rax
	movq	%rbp, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rbp, %rax
	subq	%rdx, %rax
	js	.L26
.L70:
	imulq	%rax, %rbx
	jmp	.L10
	.p2align 4,,10
	.p2align 3
.L26:
	addq	$1000000007, %rax
	jmp	.L70
	.p2align 4,,10
	.p2align 3
.L18:
	subq	$1, %rsi
	je	.L76
.L28:
	movabsq	$-8543223828751151131, %rdi
	movq	%r12, %rdx
	testb	$1, %sil
	je	.L21
	jmp	.L22
	.p2align 4,,10
	.p2align 3
.L63:
	testb	$1, %sil
	jne	.L22
.L21:
	imulq	%rdx, %rdx
	movq	%rsi, %rax
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rdx, %rax
	movq	%rdx, %rcx
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	movq	%rcx, %rdx
	subq	%rax, %rdx
	sarq	%rsi
	jne	.L63
.L20:
	movabsq	$-8543223828751151131, %rdx
	movq	%r12, %rax
	imulq	%rdx
	leaq	(%rdx,%r12), %rax
	movq	%r12, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%r12, %rax
	subq	%rdx, %rax
	jns	.L69
	addq	$1000000007, %rax
.L69:
	imulq	%rax, %rbp
	jmp	.L15
.L22:
	movq	%rdx, %rdi
	subq	$1, %rsi
	movq	%rdx, 8(%rsp)
	call	power
	movq	8(%rsp), %rdx
	imulq	%rdx, %rax
	movabsq	$-8543223828751151131, %rdx
	movq	%rax, %rcx
	imulq	%rdx
	leaq	(%rdx,%rcx), %rax
	movq	%rcx, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rcx, %rax
	subq	%rdx, %rax
	js	.L24
.L68:
	imulq	%rax, %r12
	jmp	.L20
.L32:
	.cfi_def_cfa_offset 8
	.cfi_restore 3
	.cfi_restore 6
	.cfi_restore 12
	movl	$1, %eax
	ret
.L71:
	.cfi_def_cfa_offset 48
	.cfi_offset 3, -32
	.cfi_offset 6, -24
	.cfi_offset 12, -16
	subq	$1, %rsi
	jne	.L31
	jmp	.L10
.L24:
	addq	$1000000007, %rax
	jmp	.L68
.L74:
	imulq	%rbp, %rbx
	jmp	.L10
.L73:
	subq	$1, %rsi
	jne	.L30
	jmp	.L15
	.p2align 4,,10
	.p2align 3
.L72:
	movq	%rbx, %rax
	jmp	.L4
.L75:
	subq	$1, %rsi
	jne	.L28
	jmp	.L20
.L76:
	imulq	%r12, %rbp
	jmp	.L15
	.cfi_endproc
.LFE40:
	.size	power, .-power
	.p2align 4
	.globl	inverse
	.type	inverse, @function
inverse:
.LFB41:
	.cfi_startproc
	endbr64
	movq	%rdi, %rcx
	movq	%rdi, %r10
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	imulq	%rdi, %rcx
	movabsq	$-8543223828751151131, %rdi
	movq	%rcx, %rax
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	imulq	%rcx, %rcx
	movq	%rcx, %rax
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movq	%rcx, %r9
	movq	%rcx, %r8
	movl	$250000000, %ecx
	jmp	.L78
	.p2align 4,,10
	.p2align 3
.L98:
	testb	$1, %cl
	jne	.L79
.L78:
	movq	%r8, %rsi
	movq	%rcx, %rax
	imulq	%r8, %rsi
	shrq	$63, %rax
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	sarq	%rcx
	movq	%rsi, %r8
	jne	.L98
.L80:
	movabsq	$-8543223828751151131, %rdx
	imulq	%r10, %r9
	movq	%r9, %rax
	imulq	%rdx
	leaq	(%rdx,%r9), %rax
	movq	%r9, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%r9, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	addq	$24, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 8
	ret
	.p2align 4,,10
	.p2align 3
.L79:
	.cfi_restore_state
	subq	$1, %rcx
	je	.L105
	movabsq	$-8543223828751151131, %rdi
	movq	%r8, %rdx
	testb	$1, %cl
	je	.L82
	jmp	.L83
	.p2align 4,,10
	.p2align 3
.L99:
	testb	$1, %cl
	jne	.L83
.L82:
	movq	%rdx, %rsi
	movq	%rcx, %rax
	imulq	%rdx, %rsi
	shrq	$63, %rax
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%rdi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	sarq	%rcx
	movq	%rsi, %rdx
	jne	.L99
.L84:
	movabsq	$-8543223828751151131, %rdx
	imulq	%r9, %r8
	movq	%r8, %rax
	mulq	%rdx
.L104:
	shrq	$29, %rdx
	movq	%r8, %r9
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %r9
	jmp	.L80
.L83:
	leaq	-1(%rcx), %rsi
	movq	%rdx, %rdi
	movq	%rdx, 8(%rsp)
	call	power
	movq	8(%rsp), %rdx
	movabsq	$-8543223828751151131, %rsi
	imulq	%rax, %rdx
	movq	%rdx, %rax
	movq	%rdx, %rcx
	imulq	%rsi
	leaq	(%rdx,%rcx), %rax
	movq	%rcx, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rcx, %rax
	subq	%rdx, %rax
	js	.L86
	movq	%r8, %rcx
	imulq	%rax, %rcx
.L103:
	movq	%rcx, %rax
	mulq	%rsi
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movq	%rcx, %r8
	jmp	.L84
.L86:
	leaq	1000000007(%rax), %rcx
	imulq	%r8, %rcx
	jmp	.L103
.L105:
	imulq	%r9, %r8
	movq	%r8, %rax
	mulq	%rdi
	jmp	.L104
	.cfi_endproc
.LFE41:
	.size	inverse, .-inverse
	.p2align 4
	.globl	comb
	.type	comb, @function
comb:
.LFB42:
	.cfi_startproc
	endbr64
	testq	%rsi, %rsi
	js	.L109
	cmpq	%rdi, %rsi
	jg	.L109
	movq	fact_inv(%rip), %rdx
	movq	%rdi, %rax
	movabsq	$-8543223828751151131, %rcx
	subq	%rsi, %rax
	movq	(%rdx,%rax,8), %rax
	imulq	(%rdx,%rsi,8), %rax
	movq	%rax, %rsi
	imulq	%rcx
	leaq	(%rdx,%rsi), %rax
	movq	%rsi, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rsi, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	movq	fact(%rip), %rdx
	imulq	(%rdx,%rdi,8), %rax
	movq	%rax, %rsi
	imulq	%rcx
	leaq	(%rdx,%rsi), %rax
	movq	%rsi, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rsi, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	ret
	.p2align 4,,10
	.p2align 3
.L109:
	xorl	%eax, %eax
	ret
	.cfi_endproc
.LFE42:
	.size	comb, .-comb
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"%lld%lld"
.LC1:
	.string	"%lld\n"
	.section	.text.startup,"ax",@progbits
	.p2align 4
	.globl	main
	.type	main, @function
main:
.LFB43:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	leaq	.LC0(%rip), %rdi
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	subq	$104, %rsp
	.cfi_def_cfa_offset 160
	movq	%fs:40, %rax
	movq	%rax, 88(%rsp)
	xorl	%eax, %eax
	leaq	80(%rsp), %rdx
	leaq	72(%rsp), %rsi
	call	__isoc99_scanf@PLT
	movq	72(%rsp), %rbx
	movq	80(%rsp), %rbp
	leaq	(%rbx,%rbp), %r12
	leaq	8(,%r12,8), %r15
	movq	%r15, %rdi
	call	malloc@PLT
	movq	%rax, (%rsp)
	movq	%rax, fact(%rip)
	movq	$1, (%rax)
	testq	%r12, %r12
	jle	.L341
	movq	$1, 8(%rax)
	movq	(%rsp), %r8
	movl	$1, %eax
	movl	$2, %ecx
	movabsq	$-8543223828751151131, %rdi
	cmpq	$1, %r12
	jne	.L114
	jmp	.L115
	.p2align 4,,10
	.p2align 3
.L213:
	movq	%rdx, %rcx
.L114:
	imulq	%rcx, %rax
	movq	%rax, %rsi
	imulq	%rdi
	leaq	(%rdx,%rsi), %rax
	movq	%rsi, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rsi, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	leaq	1(%rcx), %rdx
	movq	%rax, (%r8,%rcx,8)
	cmpq	%rcx, %r12
	jne	.L213
.L115:
	movq	%r15, %rdi
	call	malloc@PLT
	movq	%rax, 16(%rsp)
	movq	%rax, fact_inv(%rip)
.L211:
	movq	%rbp, 8(%rsp)
	movq	%rbx, %rbp
	xorl	%r13d, %r13d
	movq	(%rsp), %r14
	movabsq	$-8543223828751151131, %r11
	movq	16(%rsp), %rbx
.L126:
	movq	(%r14,%r13,8), %r10
	movq	%r10, %rsi
	imulq	%r10, %rsi
	movq	%rsi, %rax
	mulq	%r11
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	imulq	%rsi, %rsi
	movq	%rsi, %rax
	mulq	%r11
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movl	$250000000, %eax
	movq	%rsi, %r9
	movq	%rsi, %r8
	jmp	.L117
	.p2align 4,,10
	.p2align 3
.L298:
	testb	$1, %al
	jne	.L118
.L117:
	movq	%r8, %rdi
	movq	%rax, %rdx
	imulq	%r8, %rdi
	shrq	$63, %rdx
	leaq	(%rdx,%rax), %rsi
	movq	%rdi, %rax
	mulq	%r11
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rdi
	movq	%rsi, %rax
	sarq	%rax
	movq	%rdi, %r8
	jne	.L298
.L119:
	imulq	%r9, %r10
	movq	%r10, %rax
	imulq	%r11
	movq	%r10, %rax
	sarq	$63, %rax
	addq	%r10, %rdx
	sarq	$29, %rdx
	subq	%rax, %rdx
	imulq	$1000000007, %rdx, %rax
	movq	%r10, %rdx
	subq	%rax, %rdx
	leaq	1000000007(%rdx), %rax
	cmovs	%rax, %rdx
	movq	%rdx, (%rbx,%r13,8)
	addq	$1, %r13
	cmpq	%r13, %r12
	jge	.L126
	movq	%rbp, %rbx
	movq	8(%rsp), %rbp
.L116:
	movq	%r15, %rdi
	call	malloc@PLT
	movq	%r15, %rdi
	movq	%rax, %r13
	call	malloc@PLT
	movq	%r15, %rdi
	movq	%rax, %r14
	call	malloc@PLT
	movq	%rax, 24(%rsp)
	testq	%rbp, %rbp
	jle	.L130
	leaq	0(,%rbp,8), %rdx
	xorl	%esi, %esi
	movq	%r13, %rdi
	call	memset@PLT
.L130:
	cmpq	%r12, %rbp
	jge	.L129
	movq	16(%rsp), %rdi
	leaq	-1(%rbp), %rax
	movq	%rbp, %rdx
	movq	%r14, 32(%rsp)
	movq	%rax, %rsi
	negq	%rdx
	movq	%rbx, 40(%rsp)
	movabsq	$-8543223828751151131, %r10
	leaq	(%rdi,%rax,8), %r15
	shrq	$63, %rsi
	leaq	(%rdi,%rdx,8), %rdi
	movq	-8(%r13,%rbp,8), %rbx
	movq	%rdi, 8(%rsp)
	movl	%esi, %r14d
	testq	%rax, %rax
	js	.L216
	.p2align 4,,10
	.p2align 3
.L343:
	testb	%r14b, %r14b
	jne	.L216
	movq	8(%rsp), %rax
	movq	(%r15), %rcx
	movq	(%rsp), %rdi
	imulq	(%rax,%rbp,8), %rcx
	movq	%rcx, %rax
	imulq	%r10
	leaq	(%rdx,%rcx), %rax
	movq	%rcx, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rcx, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	imulq	-8(%rdi,%rbp,8), %rax
	movq	%rax, %rcx
	imulq	%r10
	movq	%rcx, %rax
	sarq	$63, %rax
	leaq	(%rdx,%rcx), %r11
	sarq	$29, %r11
	subq	%rax, %r11
	imulq	$1000000007, %r11, %rax
	subq	%rax, %rcx
	movq	%rcx, %r11
	leaq	1000000007(%rcx), %rax
	cmovs	%rax, %r11
.L133:
	testq	%rbp, %rbp
	je	.L219
	movl	$2, %r8d
	movq	%rbp, %rax
	movq	%r8, %rdx
	testb	$1, %bpl
	je	.L136
	jmp	.L137
	.p2align 4,,10
	.p2align 3
.L300:
	testb	$1, %al
	jne	.L319
.L136:
	movq	%rdx, %rsi
	movq	%rax, %rcx
	imulq	%rdx, %rsi
	shrq	$63, %rcx
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movq	%rcx, %rax
	sarq	%rax
	movq	%rsi, %rdx
	jne	.L300
.L219:
	movl	$1, %r8d
.L135:
	movq	%r8, %rcx
	imulq	%r8, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	imulq	%rcx, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movl	$250000000, %eax
	movq	%rcx, %r9
	jmp	.L151
	.p2align 4,,10
	.p2align 3
.L304:
	testb	$1, %al
	jne	.L152
.L151:
	movq	%rcx, %rdi
	movq	%rax, %rdx
	imulq	%rcx, %rdi
	shrq	$63, %rdx
	leaq	(%rdx,%rax), %rsi
	movq	%rdi, %rax
	mulq	%r10
	movq	%rdx, %rcx
	shrq	$29, %rcx
	imulq	$1000000007, %rcx, %rax
	subq	%rax, %rdi
	movq	%rsi, %rax
	sarq	%rax
	movq	%rdi, %rcx
	jne	.L304
.L153:
	movq	%r8, %rcx
	imulq	%r9, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rdx
	subq	%rdx, %rcx
	imulq	%r11, %rcx
	addq	%rbx, %rcx
	movq	%rcx, %rax
	imulq	%r10
	movq	%rcx, %rax
	sarq	$63, %rax
	addq	%rcx, %rdx
	sarq	$29, %rdx
	subq	%rax, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movq	%rcx, %rdx
	leaq	1000000007(%rcx), %rax
	cmovs	%rax, %rdx
	movq	%rdx, 0(%r13,%rbp,8)
	addq	$1, %rbp
	cmpq	%rbp, %r12
	je	.L342
	leaq	-1(%rbp), %rax
	movq	-8(%r13,%rbp,8), %rbx
	testq	%rax, %rax
	jns	.L343
.L216:
	xorl	%r11d, %r11d
	jmp	.L133
	.p2align 4,,10
	.p2align 3
.L118:
	subq	$1, %rax
	movq	%rax, %rsi
	je	.L344
	movq	%r8, %rdx
	testb	$1, %sil
	je	.L121
	jmp	.L122
	.p2align 4,,10
	.p2align 3
.L299:
	testb	$1, %sil
	jne	.L122
.L121:
	movq	%rdx, %rdi
	movq	%rsi, %rax
	imulq	%rdx, %rdi
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rdi, %rax
	mulq	%r11
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rdi
	sarq	%rsi
	movq	%rdi, %rdx
	jne	.L299
	movl	$1, %esi
.L123:
	imulq	%r8, %rsi
	movq	%rsi, %rax
	mulq	%r11
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	imulq	%r9, %rsi
	movq	%rsi, %rax
	mulq	%r11
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movq	%rsi, %r9
	jmp	.L119
	.p2align 4,,10
	.p2align 3
.L319:
	movq	%rdx, %r8
.L137:
	subq	$1, %rax
	je	.L135
	movq	%r8, %r9
	movq	%r8, %rdx
	testb	$1, %al
	jne	.L141
	.p2align 4,,10
	.p2align 3
.L140:
	movq	%rdx, %rsi
	movq	%rax, %rcx
	imulq	%rdx, %rsi
	shrq	$63, %rcx
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movq	%rcx, %rax
	sarq	%rax
	movq	%rsi, %rdx
	je	.L135
	testb	$1, %al
	je	.L140
	movq	%rdx, %r9
.L141:
	subq	$1, %rax
	je	.L143
	movq	%r9, %rcx
	movq	%r9, %rdx
	testb	$1, %al
	je	.L144
	jmp	.L145
	.p2align 4,,10
	.p2align 3
.L302:
	testb	$1, %al
	jne	.L323
.L144:
	movq	%rdx, %rsi
	movq	%rax, %rcx
	imulq	%rdx, %rsi
	shrq	$63, %rcx
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movq	%rcx, %rax
	sarq	%rax
	movq	%rsi, %rdx
	jne	.L302
.L143:
	imulq	%r8, %r9
	movq	%r9, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %r9
	movq	%r9, %r8
	jmp	.L135
	.p2align 4,,10
	.p2align 3
.L342:
	movq	32(%rsp), %r14
	movq	40(%rsp), %rbx
.L129:
	movq	$1, 0(%r13,%r12,8)
	testq	%rbx, %rbx
	jle	.L132
	leaq	0(,%rbx,8), %rdx
	xorl	%esi, %esi
	movq	%r14, %rdi
	call	memset@PLT
.L132:
	cmpq	%r12, %rbx
	jge	.L161
	movq	16(%rsp), %rdi
	leaq	-1(%rbx), %rax
	movq	%rbx, %rdx
	movq	%r13, 16(%rsp)
	movq	%rax, %rsi
	negq	%rdx
	movq	-8(%r14,%rbx,8), %rbp
	movabsq	$-8543223828751151131, %r10
	leaq	(%rdi,%rax,8), %rcx
	shrq	$63, %rsi
	leaq	(%rdi,%rdx,8), %rdi
	movq	%rdi, 8(%rsp)
	movq	%rcx, %r15
	movl	%esi, %r13d
	testq	%rax, %rax
	js	.L229
	.p2align 4,,10
	.p2align 3
.L346:
	testb	%r13b, %r13b
	jne	.L229
	movq	8(%rsp), %rax
	movq	(%r15), %rcx
	movq	(%rsp), %rdi
	imulq	(%rax,%rbx,8), %rcx
	movq	%rcx, %rax
	imulq	%r10
	leaq	(%rdx,%rcx), %rax
	movq	%rcx, %rdx
	sarq	$63, %rdx
	sarq	$29, %rax
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rcx, %rax
	subq	%rdx, %rax
	leaq	1000000007(%rax), %rdx
	cmovs	%rdx, %rax
	imulq	-8(%rdi,%rbx,8), %rax
	movq	%rax, %rcx
	imulq	%r10
	movq	%rcx, %rax
	sarq	$63, %rax
	leaq	(%rdx,%rcx), %r11
	sarq	$29, %r11
	subq	%rax, %r11
	imulq	$1000000007, %r11, %rax
	subq	%rax, %rcx
	movq	%rcx, %r11
	leaq	1000000007(%rcx), %rax
	cmovs	%rax, %r11
.L164:
	testq	%rbx, %rbx
	je	.L232
	movl	$2, %r8d
	movq	%rbx, %rax
	movq	%r8, %rdx
	testb	$1, %bl
	je	.L167
	jmp	.L168
	.p2align 4,,10
	.p2align 3
.L306:
	testb	$1, %al
	jne	.L330
.L167:
	movq	%rdx, %rsi
	movq	%rax, %rcx
	imulq	%rdx, %rsi
	shrq	$63, %rcx
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movq	%rcx, %rax
	sarq	%rax
	movq	%rsi, %rdx
	jne	.L306
.L232:
	movl	$1, %r8d
.L166:
	movq	%r8, %rcx
	imulq	%r8, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	imulq	%rcx, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movl	$250000000, %eax
	movq	%rcx, %r9
	jmp	.L182
	.p2align 4,,10
	.p2align 3
.L310:
	testb	$1, %al
	jne	.L183
.L182:
	movq	%rcx, %rdi
	movq	%rax, %rdx
	imulq	%rcx, %rdi
	shrq	$63, %rdx
	leaq	(%rdx,%rax), %rsi
	movq	%rdi, %rax
	mulq	%r10
	movq	%rdx, %rcx
	shrq	$29, %rcx
	imulq	$1000000007, %rcx, %rax
	subq	%rax, %rdi
	movq	%rsi, %rax
	sarq	%rax
	movq	%rdi, %rcx
	jne	.L310
.L184:
	movq	%r8, %rcx
	imulq	%r9, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rdx
	subq	%rdx, %rcx
	imulq	%r11, %rcx
	addq	%rbp, %rcx
	movq	%rcx, %rax
	imulq	%r10
	movq	%rcx, %rax
	sarq	$63, %rax
	addq	%rcx, %rdx
	sarq	$29, %rdx
	subq	%rax, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movq	%rcx, %rdx
	leaq	1000000007(%rcx), %rax
	cmovs	%rax, %rdx
	movq	%rdx, (%r14,%rbx,8)
	addq	$1, %rbx
	cmpq	%rbx, %r12
	je	.L345
	leaq	-1(%rbx), %rax
	movq	-8(%r14,%rbx,8), %rbp
	testq	%rax, %rax
	jns	.L346
.L229:
	xorl	%r11d, %r11d
	jmp	.L164
	.p2align 4,,10
	.p2align 3
.L330:
	movq	%rdx, %r8
.L168:
	subq	$1, %rax
	je	.L166
	movq	%r8, %r9
	movq	%r8, %rdx
	testb	$1, %al
	jne	.L172
	.p2align 4,,10
	.p2align 3
.L171:
	movq	%rdx, %rsi
	movq	%rax, %rcx
	imulq	%rdx, %rsi
	shrq	$63, %rcx
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movq	%rcx, %rax
	sarq	%rax
	movq	%rsi, %rdx
	je	.L166
	testb	$1, %al
	je	.L171
	movq	%rdx, %r9
.L172:
	subq	$1, %rax
	je	.L174
	movq	%r9, %rcx
	movq	%r9, %rdx
	testb	$1, %al
	je	.L175
	jmp	.L176
	.p2align 4,,10
	.p2align 3
.L308:
	testb	$1, %al
	jne	.L334
.L175:
	movq	%rdx, %rsi
	movq	%rax, %rcx
	imulq	%rdx, %rsi
	shrq	$63, %rcx
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	movq	%rcx, %rax
	sarq	%rax
	movq	%rsi, %rdx
	jne	.L308
.L174:
	imulq	%r8, %r9
	movq	%r9, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %r9
	movq	%r9, %r8
	jmp	.L166
	.p2align 4,,10
	.p2align 3
.L345:
	movq	16(%rsp), %r13
.L161:
	movq	$1, (%r14,%r12,8)
	movq	24(%rsp), %r9
	xorl	%esi, %esi
	movl	$1, %r8d
	movabsq	$-8543223828751151131, %rdi
	testq	%r12, %r12
	jle	.L163
	.p2align 4,,10
	.p2align 3
.L162:
	movq	%r8, %rcx
	subq	0(%r13,%rsi,8), %rcx
	subq	(%r14,%rsi,8), %rcx
	movq	%rcx, %rax
	imulq	%rdi
	movq	%rcx, %rax
	sarq	$63, %rax
	addq	%rcx, %rdx
	sarq	$29, %rdx
	subq	%rax, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movq	%rcx, %rdx
	leaq	1000000007(%rcx), %rax
	cmovs	%rax, %rdx
	movq	%rdx, (%r9,%rsi,8)
	addq	$1, %rsi
	cmpq	%rsi, %r12
	jne	.L162
	movq	24(%rsp), %r14
	leaq	.LC1(%rip), %rbx
	movabsq	$-8543223828751151131, %rbp
	movq	$0, (%r14,%r12,8)
	movl	$1, %r12d
	.p2align 4,,10
	.p2align 3
.L202:
	movq	-8(%r13,%r12,8), %r9
	movl	$16, %r8d
	movl	$250000000, %ecx
	jmp	.L193
	.p2align 4,,10
	.p2align 3
.L314:
	testb	$1, %cl
	jne	.L194
.L193:
	movq	%r8, %rsi
	movq	%rcx, %rax
	imulq	%r8, %rsi
	shrq	$63, %rax
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%rbp
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	sarq	%rcx
	movq	%rsi, %r8
	jne	.L314
	movl	$16, %ecx
.L195:
	addq	%rcx, %rcx
	movq	%rbx, %rsi
	movl	$1, %edi
	movq	%rcx, %rax
	mulq	%rbp
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rdx
	subq	%rdx, %rcx
	imulq	-8(%r14,%r12,8), %rcx
	addq	%r9, %rcx
	movq	%rcx, %rax
	imulq	%rbp
	movq	%rcx, %rax
	sarq	$63, %rax
	addq	%rcx, %rdx
	sarq	$29, %rdx
	subq	%rax, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	leaq	1000000007(%rcx), %rax
	movq	%rcx, %rdx
	cmovs	%rax, %rdx
	xorl	%eax, %eax
	addq	$1, %r12
	call	__printf_chk@PLT
	movq	80(%rsp), %rax
	addq	72(%rsp), %rax
	cmpq	%r12, %rax
	jge	.L202
.L163:
	movq	88(%rsp), %rax
	subq	%fs:40, %rax
	jne	.L347
	addq	$104, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	xorl	%eax, %eax
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.p2align 4,,10
	.p2align 3
.L152:
	.cfi_restore_state
	subq	$1, %rax
	movq	%rax, %rsi
	je	.L227
	movq	%rcx, %rdx
	testb	$1, %al
	je	.L156
	jmp	.L157
	.p2align 4,,10
	.p2align 3
.L305:
	testb	$1, %sil
	jne	.L157
.L156:
	movq	%rdx, %rdi
	movq	%rsi, %rax
	imulq	%rdx, %rdi
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rdi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rdi
	sarq	%rsi
	movq	%rdi, %rdx
	jne	.L305
.L227:
	movl	$1, %edx
.L155:
	movq	%rcx, %rax
	movl	$1000000007, %esi
	imulq	%rdx, %rax
	cqto
	idivq	%rsi
	movq	%rdx, %rax
	imulq	%r9, %rax
	cqto
	idivq	%rsi
	movq	%rdx, %r9
	jmp	.L153
	.p2align 4,,10
	.p2align 3
.L183:
	subq	$1, %rax
	movq	%rax, %rsi
	je	.L240
	movq	%rcx, %rdx
	testb	$1, %al
	je	.L187
	jmp	.L188
	.p2align 4,,10
	.p2align 3
.L311:
	testb	$1, %sil
	jne	.L188
.L187:
	movq	%rdx, %rdi
	movq	%rsi, %rax
	imulq	%rdx, %rdi
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rdi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rdi
	sarq	%rsi
	movq	%rdi, %rdx
	jne	.L311
.L240:
	movl	$1, %edx
.L186:
	movq	%rcx, %rax
	movl	$1000000007, %esi
	imulq	%rdx, %rax
	cqto
	idivq	%rsi
	movq	%rdx, %rax
	imulq	%r9, %rax
	cqto
	idivq	%rsi
	movq	%rdx, %r9
	jmp	.L184
	.p2align 4,,10
	.p2align 3
.L334:
	movq	%rdx, %rcx
.L176:
	subq	$1, %rax
	movq	%rax, %rsi
	je	.L237
	movq	%rcx, %rdx
	testb	$1, %al
	je	.L179
	jmp	.L180
	.p2align 4,,10
	.p2align 3
.L309:
	testb	$1, %sil
	jne	.L180
.L179:
	movq	%rdx, %rdi
	movq	%rsi, %rax
	imulq	%rdx, %rdi
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rdi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rdi
	sarq	%rsi
	movq	%rdi, %rdx
	jne	.L309
.L237:
	movl	$1, %edx
.L178:
	imulq	%rdx, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	imulq	%r9, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movq	%rcx, %r9
	jmp	.L174
	.p2align 4,,10
	.p2align 3
.L323:
	movq	%rdx, %rcx
.L145:
	subq	$1, %rax
	movq	%rax, %rsi
	je	.L224
	movq	%rcx, %rdx
	testb	$1, %al
	je	.L148
	jmp	.L149
	.p2align 4,,10
	.p2align 3
.L303:
	testb	$1, %sil
	jne	.L149
.L148:
	movq	%rdx, %rdi
	movq	%rsi, %rax
	imulq	%rdx, %rdi
	shrq	$63, %rax
	addq	%rax, %rsi
	movq	%rdi, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rdi
	sarq	%rsi
	movq	%rdi, %rdx
	jne	.L303
.L224:
	movl	$1, %edx
.L147:
	imulq	%rdx, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	imulq	%r9, %rcx
	movq	%rcx, %rax
	mulq	%r10
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rcx
	movq	%rcx, %r9
	jmp	.L143
	.p2align 4,,10
	.p2align 3
.L194:
	subq	$1, %rcx
	je	.L348
	movq	%r8, %rdx
	testb	$1, %cl
	je	.L197
	jmp	.L198
	.p2align 4,,10
	.p2align 3
.L315:
	testb	$1, %cl
	jne	.L198
.L197:
	movq	%rdx, %rsi
	movq	%rcx, %rax
	imulq	%rdx, %rsi
	shrq	$63, %rax
	addq	%rax, %rcx
	movq	%rsi, %rax
	mulq	%rbp
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	sarq	%rcx
	movq	%rsi, %rdx
	jne	.L315
	movl	$1, %esi
.L199:
	imulq	%r8, %rsi
	movq	%rsi, %rax
	mulq	%rbp
	shrq	$29, %rdx
	imulq	$1000000007, %rdx, %rax
	subq	%rax, %rsi
	salq	$4, %rsi
	movq	%rsi, %rax
	mulq	%rbp
	movq	%rdx, %rcx
	shrq	$29, %rcx
	imulq	$1000000007, %rcx, %rax
	subq	%rax, %rsi
	movq	%rsi, %rcx
	jmp	.L195
.L180:
	subq	$1, %rsi
	movq	%rdx, %rdi
	movq	%rcx, 40(%rsp)
	movq	%rdx, 32(%rsp)
	call	power
	movq	32(%rsp), %rdx
	movl	$1000000007, %esi
	movq	40(%rsp), %rcx
	imulq	%rdx, %rax
	cqto
	idivq	%rsi
	testq	%rdx, %rdx
	jns	.L178
	addq	$1000000007, %rdx
	jmp	.L178
.L149:
	subq	$1, %rsi
	movq	%rdx, %rdi
	movq	%rcx, 56(%rsp)
	movq	%rdx, 48(%rsp)
	call	power
	movq	48(%rsp), %rdx
	movl	$1000000007, %esi
	movq	56(%rsp), %rcx
	imulq	%rdx, %rax
	cqto
	idivq	%rsi
	testq	%rdx, %rdx
	jns	.L147
	addq	$1000000007, %rdx
	jmp	.L147
.L198:
	movq	%rdx, %rdi
	leaq	-1(%rcx), %rsi
	movq	%rdx, (%rsp)
	call	power
	movq	(%rsp), %rdx
	movl	$1000000007, %edi
	imulq	%rdx, %rax
	cqto
	idivq	%rdi
	movq	%rdx, %rsi
	testq	%rdx, %rdx
	jns	.L199
	addq	$1000000007, %rsi
	jmp	.L199
.L157:
	subq	$1, %rsi
	movq	%rdx, %rdi
	movq	%rcx, 56(%rsp)
	movq	%rdx, 48(%rsp)
	call	power
	movq	48(%rsp), %rdx
	movl	$1000000007, %esi
	movq	56(%rsp), %rcx
	imulq	%rdx, %rax
	cqto
	idivq	%rsi
	testq	%rdx, %rdx
	jns	.L155
	addq	$1000000007, %rdx
	jmp	.L155
.L188:
	subq	$1, %rsi
	movq	%rdx, %rdi
	movq	%rcx, 40(%rsp)
	movq	%rdx, 32(%rsp)
	call	power
	movq	32(%rsp), %rdx
	movl	$1000000007, %esi
	movq	40(%rsp), %rcx
	imulq	%rdx, %rax
	cqto
	idivq	%rsi
	testq	%rdx, %rdx
	jns	.L186
	addq	$1000000007, %rdx
	jmp	.L186
.L122:
	movq	%rdx, %rdi
	subq	$1, %rsi
	movq	%rdx, 24(%rsp)
	call	power
	movq	24(%rsp), %rdx
	movl	$1000000007, %edi
	imulq	%rdx, %rax
	cqto
	idivq	%rdi
	movq	%rdx, %rsi
	testq	%rdx, %rdx
	jns	.L123
	addq	$1000000007, %rsi
	jmp	.L123
.L341:
	movq	%r15, %rdi
	call	malloc@PLT
	movq	%rax, 16(%rsp)
	movq	%rax, fact_inv(%rip)
	testq	%r12, %r12
	jne	.L116
	jmp	.L211
.L344:
	movq	%r9, %rax
	movl	$1000000007, %edi
	imulq	%r8, %rax
	cqto
	idivq	%rdi
	movq	%rdx, %r9
	jmp	.L119
.L348:
	movq	%r8, %rax
	movl	$1000000007, %edi
	salq	$4, %rax
	cqto
	idivq	%rdi
	movq	%rdx, %rcx
	jmp	.L195
.L347:
	call	__stack_chk_fail@PLT
	.cfi_endproc
.LFE43:
	.size	main, .-main
	.globl	fact_inv
	.bss
	.align 8
	.type	fact_inv, @object
	.size	fact_inv, 8
fact_inv:
	.zero	8
	.globl	fact
	.align 8
	.type	fact, @object
	.size	fact, 8
fact:
	.zero	8
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:

#include <stdio.h>
#include <stdlib.h>
#define int long long
#define p (int)(1e9 + 7)

int MOD(int a){
	a %= p;
	return a >= 0 ? a : a + p;
}

int power(int a, int N){
	if(N == 0){
		return 1;
	}
	else if(N % 2 == 0){
		return power(MOD(a * a), N / 2);
	}
	else{
		return MOD(a * power(a, N - 1));
	}
}

int inverse(int a){
	return power(a, p - 2);
}

int *fact, *fact_inv;

int comb(int n, int k){
	if(k < 0 || n < k || n < 0){
		return 0;
	}
	else{
		return MOD(fact[n] * MOD(fact_inv[k] * fact_inv[n - k]));
	}
}

signed main(){
	int B, W, i;
	scanf("%lld%lld", &B, &W);
	fact = (int *)malloc(sizeof(int) * (B + W + 1));
	fact[0] = 1;
	for(i = 1; i <= B + W; i++){
		fact[i] = MOD(fact[i - 1] * i);
	}
	fact_inv = (int *)malloc(sizeof(int) * (B + W + 1));
	for(i = 0; i <= B + W; i++){
		fact_inv[i] = inverse(fact[i]);
	}
	int *a = (int *)malloc(sizeof(int) * (B + W + 1));
	int *b = (int *)malloc(sizeof(int) * (B + W + 1));
	int *c = (int *)malloc(sizeof(int) * (B + W + 1));
	for(i = 0; i < W; i++){
		a[i] = 0;
	}
	for(i = W; i < B + W; i++){
		a[i] = MOD(a[i - 1] + comb(i - 1, W - 1) * inverse(power(2, i)));
	}
	a[B + W] = 1;

	for(i = 0; i < B; i++){
		b[i] = 0;
	}
	for(i = B; i < B + W; i++){
		b[i] = MOD(b[i - 1] + comb(i - 1, B - 1) * inverse(power(2, i)));
	}
	b[B + W] = 1;

	for(i = 0; i < B + W; i++){
		c[i] = MOD(1 - a[i] - b[i]);
	}
	c[B + W] = 0;

/*	for(i = 0; i <= B + W; i++){
		printf("a[%lld] = %lld\n", i, a[i]);
	}
	printf("\n");

	for(i = 0; i <= B + W; i++){
		printf("b[%lld] = %lld\n", i, b[i]);
	}
	printf("\n");

	for(i = 0; i <= B + W; i++){
		printf("c[%lld] = %lld\n", i, c[i]);
	}
	printf("\n");
*/
	for(i = 1; i <= B + W; i++){
		printf("%lld\n", MOD(a[i - 1] + inverse(2) * c[i - 1]));
	}
	return 0;
}
1 2
 6 3
 1 3
 6 6
 2 3
 10 6
 2 6
 10 8
 4 6
 12 8

500000004
250000002
250000002
 500000004
500000004
500000004
62500001
906250007
750000006
882812507
449218754
449218754
 500000004
250000002
125000001
125000001
 500000004
500000004
500000004
500000004
500000004
500000004
500000004
500000004
500000004
500000004
500000004
500000004
 500000004
500000004
375000003
812500006
812500006
 500000004
500000004
500000004
500000004
500000004
500000004
70312501
781250006
775390631
767578131
723144537
536132817
287963870
86547853
485839848
485839848
 500000004
500000004
375000003
250000002
406250003
843750006
562500004
562500004
 500000004
500000004
500000004
500000004
500000004
500000004
500000004
500000004
642578130
212890627
960449226
420898441
496459965
295043948
243804934
492919926
617477422
617477422
 500000004
500000004
500000004
500000004
218750002
656250005
523437504
531250004
535156254
535156254
 500000004
500000004
500000004
500000004
500000004
500000004
500000004
500000004
642578130
212890627
496093754
634765630
441528324
166870119
628479009
108398439
822738654
167099001
339279178
339279178

Given the following C code and unoptimized assembly code, your task is to generate highly optimized x86-64 assembly code.
C Code:

```c
#include <stdio.h>
#include <stdlib.h>
#define int long long
#define p (int)(1e9 + 7)

int MOD(int a){
	a %= p;
	return a >= 0 ? a : a + p;
}

int power(int a, int N){
	if(N == 0){
		return 1;
	}
	else if(N % 2 == 0){
		return power(MOD(a * a), N / 2);
	}
	else{
		return MOD(a * power(a, N - 1));
	}
}

int inverse(int a){
	return power(a, p - 2);
}

int *fact, *fact_inv;

int comb(int n, int k){
	if(k < 0 || n < k || n < 0){
		return 0;
	}
	else{
		return MOD(fact[n] * MOD(fact_inv[k] * fact_inv[n - k]));
	}
}

signed main(){
	int B, W, i;
	scanf("%lld%lld", &B, &W);
	fact = (int *)malloc(sizeof(int) * (B + W + 1));
	fact[0] = 1;
	for(i = 1; i <= B + W; i++){
		fact[i] = MOD(fact[i - 1] * i);
	}
	fact_inv = (int *)malloc(sizeof(int) * (B + W + 1));
	for(i = 0; i <= B + W; i++){
		fact_inv[i] = inverse(fact[i]);
	}
	int *a = (int *)malloc(sizeof(int) * (B + W + 1));
	int *b = (int *)malloc(sizeof(int) * (B + W + 1));
	int *c = (int *)malloc(sizeof(int) * (B + W + 1));
	for(i = 0; i < W; i++){
		a[i] = 0;
	}
	for(i = W; i < B + W; i++){
		a[i] = MOD(a[i - 1] + comb(i - 1, W - 1) * inverse(power(2, i)));
	}
	a[B + W] = 1;

	for(i = 0; i < B; i++){
		b[i] = 0;
	}
	for(i = B; i < B + W; i++){
		b[i] = MOD(b[i - 1] + comb(i - 1, B - 1) * inverse(power(2, i)));
	}
	b[B + W] = 1;

	for(i = 0; i < B + W; i++){
		c[i] = MOD(1 - a[i] - b[i]);
	}
	c[B + W] = 0;

/*	for(i = 0; i <= B + W; i++){
		printf("a[%lld] = %lld\n", i, a[i]);
	}
	printf("\n");

	for(i = 0; i <= B + W; i++){
		printf("b[%lld] = %lld\n", i, b[i]);
	}
	printf("\n");

	for(i = 0; i <= B + W; i++){
		printf("c[%lld] = %lld\n", i, c[i]);
	}
	printf("\n");
*/
	for(i = 1; i <= B + W; i++){
		printf("%lld\n", MOD(a[i - 1] + inverse(2) * c[i - 1]));
	}
	return 0;
}```

Unoptimized Assembly Code:

```assembly
	.file	"temp.c"
	.text
	.globl	MOD
	.type	MOD, @function
MOD:
.LFB6:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, -8(%rbp)
	movq	-8(%rbp), %rcx
	movabsq	$-8543223828751151131, %rdx
	movq	%rcx, %rax
	imulq	%rdx
	leaq	(%rdx,%rcx), %rax
	sarq	$29, %rax
	movq	%rcx, %rdx
	sarq	$63, %rdx
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rcx, %rax
	subq	%rdx, %rax
	movq	%rax, -8(%rbp)
	cmpq	$0, -8(%rbp)
	jns	.L2
	movq	-8(%rbp), %rax
	addq	$1000000007, %rax
	jmp	.L4
.L2:
	movq	-8(%rbp), %rax
.L4:
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE6:
	.size	MOD, .-MOD
	.globl	power
	.type	power, @function
power:
.LFB7:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%rbx
	subq	$24, %rsp
	.cfi_offset 3, -24
	movq	%rdi, -24(%rbp)
	movq	%rsi, -32(%rbp)
	cmpq	$0, -32(%rbp)
	jne	.L6
	movl	$1, %eax
	jmp	.L7
.L6:
	movq	-32(%rbp), %rax
	andl	$1, %eax
	testq	%rax, %rax
	jne	.L8
	movq	-32(%rbp), %rax
	movq	%rax, %rdx
	shrq	$63, %rdx
	addq	%rdx, %rax
	sarq	%rax
	movq	%rax, %rbx
	movq	-24(%rbp), %rax
	imulq	%rax, %rax
	movq	%rax, %rdi
	call	MOD
	movq	%rbx, %rsi
	movq	%rax, %rdi
	call	power
	jmp	.L7
.L8:
	movq	-32(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-24(%rbp), %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	power
	imulq	-24(%rbp), %rax
	movq	%rax, %rdi
	call	MOD
.L7:
	movq	-8(%rbp), %rbx
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE7:
	.size	power, .-power
	.globl	inverse
	.type	inverse, @function
inverse:
.LFB8:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$16, %rsp
	movq	%rdi, -8(%rbp)
	movq	-8(%rbp), %rax
	movl	$1000000005, %esi
	movq	%rax, %rdi
	call	power
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE8:
	.size	inverse, .-inverse
	.globl	fact
	.bss
	.align 8
	.type	fact, @object
	.size	fact, 8
fact:
	.zero	8
	.globl	fact_inv
	.align 8
	.type	fact_inv, @object
	.size	fact_inv, 8
fact_inv:
	.zero	8
	.text
	.globl	comb
	.type	comb, @function
comb:
.LFB9:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%rbx
	subq	$16, %rsp
	.cfi_offset 3, -24
	movq	%rdi, -16(%rbp)
	movq	%rsi, -24(%rbp)
	cmpq	$0, -24(%rbp)
	js	.L12
	movq	-16(%rbp), %rax
	cmpq	-24(%rbp), %rax
	jl	.L12
	cmpq	$0, -16(%rbp)
	jns	.L13
.L12:
	movl	$0, %eax
	jmp	.L14
.L13:
	movq	fact(%rip), %rdx
	movq	-16(%rbp), %rax
	salq	$3, %rax
	addq	%rdx, %rax
	movq	(%rax), %rbx
	movq	fact_inv(%rip), %rdx
	movq	-24(%rbp), %rax
	salq	$3, %rax
	addq	%rdx, %rax
	movq	(%rax), %rdx
	movq	fact_inv(%rip), %rcx
	movq	-16(%rbp), %rax
	subq	-24(%rbp), %rax
	salq	$3, %rax
	addq	%rcx, %rax
	movq	(%rax), %rax
	imulq	%rdx, %rax
	movq	%rax, %rdi
	call	MOD
	imulq	%rbx, %rax
	movq	%rax, %rdi
	call	MOD
.L14:
	movq	-8(%rbp), %rbx
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE9:
	.size	comb, .-comb
	.section	.rodata
.LC0:
	.string	"%lld%lld"
.LC1:
	.string	"%lld\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB10:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%r12
	pushq	%rbx
	subq	$64, %rsp
	.cfi_offset 12, -24
	.cfi_offset 3, -32
	movq	%fs:40, %rax
	movq	%rax, -24(%rbp)
	xorl	%eax, %eax
	leaq	-64(%rbp), %rdx
	leaq	-72(%rbp), %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, fact(%rip)
	movq	fact(%rip), %rax
	movq	$1, (%rax)
	movq	$1, -56(%rbp)
	jmp	.L16
.L17:
	movq	fact(%rip), %rdx
	movq	-56(%rbp), %rax
	salq	$3, %rax
	subq	$8, %rax
	addq	%rdx, %rax
	movq	(%rax), %rax
	imulq	-56(%rbp), %rax
	movq	fact(%rip), %rcx
	movq	-56(%rbp), %rdx
	salq	$3, %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	MOD
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L16:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jle	.L17
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, fact_inv(%rip)
	movq	$0, -56(%rbp)
	jmp	.L18
.L19:
	movq	fact(%rip), %rdx
	movq	-56(%rbp), %rax
	salq	$3, %rax
	addq	%rdx, %rax
	movq	(%rax), %rax
	movq	fact_inv(%rip), %rcx
	movq	-56(%rbp), %rdx
	salq	$3, %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	inverse
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L18:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jle	.L19
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, -48(%rbp)
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, -40(%rbp)
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, -32(%rbp)
	movq	$0, -56(%rbp)
	jmp	.L20
.L21:
	movq	-56(%rbp), %rax
	leaq	0(,%rax,8), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	$0, (%rax)
	addq	$1, -56(%rbp)
.L20:
	movq	-64(%rbp), %rax
	cmpq	%rax, -56(%rbp)
	jl	.L21
	movq	-64(%rbp), %rax
	movq	%rax, -56(%rbp)
	jmp	.L22
.L23:
	movq	-56(%rbp), %rax
	salq	$3, %rax
	leaq	-8(%rax), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	(%rax), %r12
	movq	-64(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-56(%rbp), %rax
	subq	$1, %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	comb
	movq	%rax, %rbx
	movq	-56(%rbp), %rax
	movq	%rax, %rsi
	movl	$2, %edi
	call	power
	movq	%rax, %rdi
	call	inverse
	imulq	%rbx, %rax
	addq	%r12, %rax
	movq	-56(%rbp), %rdx
	leaq	0(,%rdx,8), %rcx
	movq	-48(%rbp), %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	MOD
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L22:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jl	.L23
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	$1, (%rax)
	movq	$0, -56(%rbp)
	jmp	.L24
.L25:
	movq	-56(%rbp), %rax
	leaq	0(,%rax,8), %rdx
	movq	-40(%rbp), %rax
	addq	%rdx, %rax
	movq	$0, (%rax)
	addq	$1, -56(%rbp)
.L24:
	movq	-72(%rbp), %rax
	cmpq	%rax, -56(%rbp)
	jl	.L25
	movq	-72(%rbp), %rax
	movq	%rax, -56(%rbp)
	jmp	.L26
.L27:
	movq	-56(%rbp), %rax
	salq	$3, %rax
	leaq	-8(%rax), %rdx
	movq	-40(%rbp), %rax
	addq	%rdx, %rax
	movq	(%rax), %r12
	movq	-72(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-56(%rbp), %rax
	subq	$1, %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	comb
	movq	%rax, %rbx
	movq	-56(%rbp), %rax
	movq	%rax, %rsi
	movl	$2, %edi
	call	power
	movq	%rax, %rdi
	call	inverse
	imulq	%rbx, %rax
	addq	%r12, %rax
	movq	-56(%rbp), %rdx
	leaq	0(,%rdx,8), %rcx
	movq	-40(%rbp), %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	MOD
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L26:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jl	.L27
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	movq	-40(%rbp), %rax
	addq	%rdx, %rax
	movq	$1, (%rax)
	movq	$0, -56(%rbp)
	jmp	.L28
.L29:
	movq	-56(%rbp), %rax
	leaq	0(,%rax,8), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	(%rax), %rax
	movl	$1, %edx
	subq	%rax, %rdx
	movq	-56(%rbp), %rax
	leaq	0(,%rax,8), %rcx
	movq	-40(%rbp), %rax
	addq	%rcx, %rax
	movq	(%rax), %rcx
	movq	%rdx, %rax
	subq	%rcx, %rax
	movq	-56(%rbp), %rdx
	leaq	0(,%rdx,8), %rcx
	movq	-32(%rbp), %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	MOD
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L28:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jl	.L29
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	movq	-32(%rbp), %rax
	addq	%rdx, %rax
	movq	$0, (%rax)
	movq	$1, -56(%rbp)
	jmp	.L30
.L31:
	movq	-56(%rbp), %rax
	salq	$3, %rax
	leaq	-8(%rax), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	(%rax), %rbx
	movl	$2, %edi
	call	inverse
	movq	-56(%rbp), %rdx
	salq	$3, %rdx
	leaq	-8(%rdx), %rcx
	movq	-32(%rbp), %rdx
	addq	%rcx, %rdx
	movq	(%rdx), %rdx
	imulq	%rdx, %rax
	addq	%rbx, %rax
	movq	%rax, %rdi
	call	MOD
	movq	%rax, %rsi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	addq	$1, -56(%rbp)
.L30:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jle	.L31
	movl	$0, %eax
	movq	-24(%rbp), %rdx
	subq	%fs:40, %rdx
	je	.L33
	call	__stack_chk_fail@PLT
.L33:
	addq	$64, %rsp
	popq	%rbx
	popq	%r12
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE10:
	.size	main, .-main
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:
```

Only output the optimized assembly code. Do not include any other text. Do not write any comments in the assembly code. Wrap the assembly code in ```assembly``` tags.
train
	.file	"temp.c"
	.text
	.globl	MOD
	.type	MOD, @function
MOD:
.LFB6:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, -8(%rbp)
	movq	-8(%rbp), %rcx
	movabsq	$-8543223828751151131, %rdx
	movq	%rcx, %rax
	imulq	%rdx
	leaq	(%rdx,%rcx), %rax
	sarq	$29, %rax
	movq	%rcx, %rdx
	sarq	$63, %rdx
	subq	%rdx, %rax
	imulq	$1000000007, %rax, %rdx
	movq	%rcx, %rax
	subq	%rdx, %rax
	movq	%rax, -8(%rbp)
	cmpq	$0, -8(%rbp)
	jns	.L2
	movq	-8(%rbp), %rax
	addq	$1000000007, %rax
	jmp	.L4
.L2:
	movq	-8(%rbp), %rax
.L4:
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE6:
	.size	MOD, .-MOD
	.globl	power
	.type	power, @function
power:
.LFB7:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%rbx
	subq	$24, %rsp
	.cfi_offset 3, -24
	movq	%rdi, -24(%rbp)
	movq	%rsi, -32(%rbp)
	cmpq	$0, -32(%rbp)
	jne	.L6
	movl	$1, %eax
	jmp	.L7
.L6:
	movq	-32(%rbp), %rax
	andl	$1, %eax
	testq	%rax, %rax
	jne	.L8
	movq	-32(%rbp), %rax
	movq	%rax, %rdx
	shrq	$63, %rdx
	addq	%rdx, %rax
	sarq	%rax
	movq	%rax, %rbx
	movq	-24(%rbp), %rax
	imulq	%rax, %rax
	movq	%rax, %rdi
	call	MOD
	movq	%rbx, %rsi
	movq	%rax, %rdi
	call	power
	jmp	.L7
.L8:
	movq	-32(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-24(%rbp), %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	power
	imulq	-24(%rbp), %rax
	movq	%rax, %rdi
	call	MOD
.L7:
	movq	-8(%rbp), %rbx
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE7:
	.size	power, .-power
	.globl	inverse
	.type	inverse, @function
inverse:
.LFB8:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$16, %rsp
	movq	%rdi, -8(%rbp)
	movq	-8(%rbp), %rax
	movl	$1000000005, %esi
	movq	%rax, %rdi
	call	power
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE8:
	.size	inverse, .-inverse
	.globl	fact
	.bss
	.align 8
	.type	fact, @object
	.size	fact, 8
fact:
	.zero	8
	.globl	fact_inv
	.align 8
	.type	fact_inv, @object
	.size	fact_inv, 8
fact_inv:
	.zero	8
	.text
	.globl	comb
	.type	comb, @function
comb:
.LFB9:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%rbx
	subq	$16, %rsp
	.cfi_offset 3, -24
	movq	%rdi, -16(%rbp)
	movq	%rsi, -24(%rbp)
	cmpq	$0, -24(%rbp)
	js	.L12
	movq	-16(%rbp), %rax
	cmpq	-24(%rbp), %rax
	jl	.L12
	cmpq	$0, -16(%rbp)
	jns	.L13
.L12:
	movl	$0, %eax
	jmp	.L14
.L13:
	movq	fact(%rip), %rdx
	movq	-16(%rbp), %rax
	salq	$3, %rax
	addq	%rdx, %rax
	movq	(%rax), %rbx
	movq	fact_inv(%rip), %rdx
	movq	-24(%rbp), %rax
	salq	$3, %rax
	addq	%rdx, %rax
	movq	(%rax), %rdx
	movq	fact_inv(%rip), %rcx
	movq	-16(%rbp), %rax
	subq	-24(%rbp), %rax
	salq	$3, %rax
	addq	%rcx, %rax
	movq	(%rax), %rax
	imulq	%rdx, %rax
	movq	%rax, %rdi
	call	MOD
	imulq	%rbx, %rax
	movq	%rax, %rdi
	call	MOD
.L14:
	movq	-8(%rbp), %rbx
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE9:
	.size	comb, .-comb
	.section	.rodata
.LC0:
	.string	"%lld%lld"
.LC1:
	.string	"%lld\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB10:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%r12
	pushq	%rbx
	subq	$64, %rsp
	.cfi_offset 12, -24
	.cfi_offset 3, -32
	movq	%fs:40, %rax
	movq	%rax, -24(%rbp)
	xorl	%eax, %eax
	leaq	-64(%rbp), %rdx
	leaq	-72(%rbp), %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, fact(%rip)
	movq	fact(%rip), %rax
	movq	$1, (%rax)
	movq	$1, -56(%rbp)
	jmp	.L16
.L17:
	movq	fact(%rip), %rdx
	movq	-56(%rbp), %rax
	salq	$3, %rax
	subq	$8, %rax
	addq	%rdx, %rax
	movq	(%rax), %rax
	imulq	-56(%rbp), %rax
	movq	fact(%rip), %rcx
	movq	-56(%rbp), %rdx
	salq	$3, %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	MOD
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L16:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jle	.L17
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, fact_inv(%rip)
	movq	$0, -56(%rbp)
	jmp	.L18
.L19:
	movq	fact(%rip), %rdx
	movq	-56(%rbp), %rax
	salq	$3, %rax
	addq	%rdx, %rax
	movq	(%rax), %rax
	movq	fact_inv(%rip), %rcx
	movq	-56(%rbp), %rdx
	salq	$3, %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	inverse
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L18:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jle	.L19
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, -48(%rbp)
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, -40(%rbp)
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	addq	$1, %rax
	salq	$3, %rax
	movq	%rax, %rdi
	call	malloc@PLT
	movq	%rax, -32(%rbp)
	movq	$0, -56(%rbp)
	jmp	.L20
.L21:
	movq	-56(%rbp), %rax
	leaq	0(,%rax,8), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	$0, (%rax)
	addq	$1, -56(%rbp)
.L20:
	movq	-64(%rbp), %rax
	cmpq	%rax, -56(%rbp)
	jl	.L21
	movq	-64(%rbp), %rax
	movq	%rax, -56(%rbp)
	jmp	.L22
.L23:
	movq	-56(%rbp), %rax
	salq	$3, %rax
	leaq	-8(%rax), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	(%rax), %r12
	movq	-64(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-56(%rbp), %rax
	subq	$1, %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	comb
	movq	%rax, %rbx
	movq	-56(%rbp), %rax
	movq	%rax, %rsi
	movl	$2, %edi
	call	power
	movq	%rax, %rdi
	call	inverse
	imulq	%rbx, %rax
	addq	%r12, %rax
	movq	-56(%rbp), %rdx
	leaq	0(,%rdx,8), %rcx
	movq	-48(%rbp), %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	MOD
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L22:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jl	.L23
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	$1, (%rax)
	movq	$0, -56(%rbp)
	jmp	.L24
.L25:
	movq	-56(%rbp), %rax
	leaq	0(,%rax,8), %rdx
	movq	-40(%rbp), %rax
	addq	%rdx, %rax
	movq	$0, (%rax)
	addq	$1, -56(%rbp)
.L24:
	movq	-72(%rbp), %rax
	cmpq	%rax, -56(%rbp)
	jl	.L25
	movq	-72(%rbp), %rax
	movq	%rax, -56(%rbp)
	jmp	.L26
.L27:
	movq	-56(%rbp), %rax
	salq	$3, %rax
	leaq	-8(%rax), %rdx
	movq	-40(%rbp), %rax
	addq	%rdx, %rax
	movq	(%rax), %r12
	movq	-72(%rbp), %rax
	leaq	-1(%rax), %rdx
	movq	-56(%rbp), %rax
	subq	$1, %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	comb
	movq	%rax, %rbx
	movq	-56(%rbp), %rax
	movq	%rax, %rsi
	movl	$2, %edi
	call	power
	movq	%rax, %rdi
	call	inverse
	imulq	%rbx, %rax
	addq	%r12, %rax
	movq	-56(%rbp), %rdx
	leaq	0(,%rdx,8), %rcx
	movq	-40(%rbp), %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	MOD
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L26:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jl	.L27
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	movq	-40(%rbp), %rax
	addq	%rdx, %rax
	movq	$1, (%rax)
	movq	$0, -56(%rbp)
	jmp	.L28
.L29:
	movq	-56(%rbp), %rax
	leaq	0(,%rax,8), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	(%rax), %rax
	movl	$1, %edx
	subq	%rax, %rdx
	movq	-56(%rbp), %rax
	leaq	0(,%rax,8), %rcx
	movq	-40(%rbp), %rax
	addq	%rcx, %rax
	movq	(%rax), %rcx
	movq	%rdx, %rax
	subq	%rcx, %rax
	movq	-56(%rbp), %rdx
	leaq	0(,%rdx,8), %rcx
	movq	-32(%rbp), %rdx
	leaq	(%rcx,%rdx), %rbx
	movq	%rax, %rdi
	call	MOD
	movq	%rax, (%rbx)
	addq	$1, -56(%rbp)
.L28:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jl	.L29
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	movq	-32(%rbp), %rax
	addq	%rdx, %rax
	movq	$0, (%rax)
	movq	$1, -56(%rbp)
	jmp	.L30
.L31:
	movq	-56(%rbp), %rax
	salq	$3, %rax
	leaq	-8(%rax), %rdx
	movq	-48(%rbp), %rax
	addq	%rdx, %rax
	movq	(%rax), %rbx
	movl	$2, %edi
	call	inverse
	movq	-56(%rbp), %rdx
	salq	$3, %rdx
	leaq	-8(%rdx), %rcx
	movq	-32(%rbp), %rdx
	addq	%rcx, %rdx
	movq	(%rdx), %rdx
	imulq	%rdx, %rax
	addq	%rbx, %rax
	movq	%rax, %rdi
	call	MOD
	movq	%rax, %rsi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	addq	$1, -56(%rbp)
.L30:
	movq	-72(%rbp), %rdx
	movq	-64(%rbp), %rax
	addq	%rdx, %rax
	cmpq	%rax, -56(%rbp)
	jle	.L31
	movl	$0, %eax
	movq	-24(%rbp), %rdx
	subq	%fs:40, %rdx
	je	.L33
	call	__stack_chk_fail@PLT
.L33:
	addq	$64, %rsp
	popq	%rbx
	popq	%r12
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE10:
	.size	main, .-main
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:
