抱歉，这没有集美
题号：NC245517
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

众所周知，集美大学的新生开学仪式（并不）是这样的：
  1. 今年预计招收n名新生，将他们依次按照编号。
  2. 拿来n个球，也是按照编号，然后将其打乱后发放给新生，第i位新生分到的球编号为p_i。
  3. 若对于某个一个编号为i的新生，gcd(p_i,i)为偶数，则被认定为天选之子，他将会变身为集美。其中表示x和y的最大公约数。
Tenshi是集美大学2023年的新生，他酷爱女装，所以他一直梦想变成集美。因为出于对新生隐私的保护，贝贝并不知道Tenshi的编号，他想先计算下有多少种发球方案能让Tenshi变身为集美的概率不为0（即一个方案至少存在一个位置能变身集美，则概率就不为0）。

输入描述:

仅一行，包含一个整数，表示新生的数量。

输出描述:

输出一行，包含一个整数，如题意所示，答案取模。
示例1

输入

复制 
4

输出

复制 
20

说明

20种方案依次为：
1, 2, 3, 4
1, 2, 4, 3
1, 3, 2, 4
1, 3, 4, 2
1, 4, 2, 3
1, 4, 3, 2
2, 1, 3, 4
2, 3, 1, 4
2, 4, 1, 3
2, 4, 3, 1
3, 1, 2, 4
3, 1, 4, 2
3, 2, 1, 4
3, 2, 4, 1
3, 4, 1, 2
3, 4, 2, 1
4, 1, 3, 2
4, 2, 1, 3
4, 2, 3, 1
4, 3, 1, 2
示例2

输入

复制 
114514

输出

复制 
731904262