#include typedef long long int ll; using namespace std; const int MOD = 1000000007; const int INF = 1000000; ll N; int main(){ ios_base::sync_with_stdio(false); cin>>N; cout<