荒神在此
题号:NC236761
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述


给出一个数字  ,求有多少个长度为  的序列  (下标为  )。
要求满足

  1. 对于所有   ,  。
  2.    是一个奇数。

因为答案可能很大,所以你需要输出答案对  取模。

输入描述:

第一行给出一个正整数   。

输出描述:

输出一行一个整数表示对  取模后的答案。
示例1

输入

复制
2

输出

复制
3