逆序对
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

求所有长度为n的01串中满足如下条件的二元组个数:
设第i位和第j位分别位ai和aj(i<j),则ai=1,aj=0。
答案对1e9+7取模。

输入描述:

输入一个n。

输出描述:

输出答案对1e9+7取模
示例1

输入

复制
3

输出

复制
6

说明


备注:

 n <= 1018