【题目描述】

现定义一个函数F(a,b)，表示对于数对(a,b)调用辗转相除法的步数为多少。

已知F(a,b)=k，求(a,b)使得a+b尽量小，答案模10⁹+7。

【输入描述】

输入一个整数，表示k。

【输出描述】

输出两个整数，表示a、b(a < b)。

【输入样例】

1000000007

【输出样例】

0 1000000006

【数据范围及提示】

对于10%的数据，k < 10；

对于40%的数据，k < 50；

对于60%的数据，k < 10⁸；

对于90%的数据，k < 10¹⁰；

对于100%的数据，k < 10¹⁵。

辗转相除