小a的旅行计划

题号：NC20808
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

小a终于放假了，它想在假期中去一些地方游玩，现在有N个景点，编号为 $1, 2, \dots N$ ，同时小b也想出去游玩。由于一些特殊♂原因，他们的旅行计划必须满足一些条件

首先，他们可以从这N个景点中任意选几个游玩

设小a选出的景点集合为A，小b选的景点集合为B，则需要满足

1. A,B的交集不能为空集

2. A,B不能相互包含(A=B也属于相互包含)

注意：在这里我们认为(A,B)是无序的，即(A,B)和(B,A)是同一种方案

一个整数N表示景点的数量

一个整数表示方案数，答案对取模

示例1

复制

复制

合法的方案如下：
小a：(1, 2) 小b： (2, 3)
小a：(1, 3) 小b： (2, 3)
小a：(1, 2) 小b： (1, 3)

示例2

复制

复制

示例3

复制

复制

示例4

复制

复制

68735934

示例5

复制

复制

对于100%的数据