Link-Kəs Dumplinqləri

Chmyaaax dumplinqləri çox sevir, ona görə də LCOI (Link-Kəs İnformatika Olimpiadası) dan gəldikdən sonra bir neçə ədəd yeməyə qərar verdi. Amma, təəssüf ki, o, olimpiadada olduğu zaman Link-Kəs sistemi yenidən qurulmuşdu.

İndi sistem $n$ tərəfli kvadrat şəklində məhdud bir təyyarədir, bu kvadratın küncləri $(0;0)$, $(0;n)$, $(n;0)$ və $(n;n)$ nöqtələrində yerləşir. Hər bir nöqtədə dumplinqləri almaq üçün restoran var. Həmçinin, $(x;y)$ nöqtəsindəki restoranın dumplinqlərinin dadını müəyyən edən $f(x,y)$ funksiyası var:

burada $\oplus$ işarəsi bitwise XOR əməliyyatını, $|$ işarəsi — bitwise OR əməliyyatını və $\&$ işarəsi — bitwise AND əməliyyatını təmsil edir.

Chmyaaax Link-Kəs sistemində tapa biləcəyi ən dadlı dumplinqləri dadmaq istəyir, buna görə də sistemdəki bütün $(n+1)\times (n+1)$ restoranlar arasında ən böyük dadlılığı və bu dadlılığa sahib restoranların sayını bilmək istəyir. Zəhmət olmasa, ona bu iki dəyəri müəyyən etməyə kömək edin.

Restoranların sayı çox ola biləcəyindən, zəhmət olmasa, bu dəyəri $10^9+7$ modulunda çıxarın.

Giriş verilənləri

Tək bir sətir bir tam ədəd $n$ ($1\le n<2^{60}$) ehtiva edir — Link-Kəs sisteminin tərəf uzunluğu.

Çıxış verilənləri

Tək bir sətirdə, bütün restoranlar arasında tapıla biləcək dumplinqlərin maksimum dadlılığı və bu dadlılıq dəyərinə sahib restoranların sayını $10^9+7$ modulunda çıxarmaqla iki tam ədəd çıxarmalısınız. Zəhmət olmasa, maksimum dadlılığı cavabda olduğu kimi çıxarın (yəni, modulo $10^9+7$ deyil).

Nümunələr

Qeyd

Birinci nümunədə, burada $16$ nöqtə və onlardakı restoranlarda dumplinqlərin dadlılıq dəyərləri:

1. $(0,0)$: $f(0,0)=0+0+0=$0$;$

2. $(0,1)$: $f(0,1)=1+1+0=$2$;$

3. $(0,2)$: $f(0,2)=2+2+0=$4$;$

4. $(0,3)$: $f(0,3)=3+3+0=$6$;$

5. $(1,0)$: $f(1,0)=1+1+0=$2$;$

6. $(1,1)$: $f(1,1)=0+1+1=$2$;$

7. $(1,2)$: $f(1,2)=3+3+0=$6$;$

8. $(1,3)$: $f(1,3)=2+3+1=$6$;$

9. $(2,0)$: $f(2,0)=2+2+0=$4$;$

10. $(2,1)$: $f(2,1)=3+3+0=$6$;$

11. $(2,2)$: $f(2,2)=0+2+2=$4$;$

12. $(2,3)$: $f(2,3)=1+3+2=$6$;$

13. $(3,0)$: $f(3,0)=3+3+0=$6$;$

14. $(3,1)$: $f(3,1)=2+3+1=$6$;$

15. $(3,2)$: $f(3,2)=1+3+2=$6$;$

16. $(3,3)$: $f(3,3)=0+3+3=$6$.$

Gördüyümüz kimi, bu restoranların maksimum dadlılığı $6$-dır və bu dəyərə sahib $9$ nöqtə var.

İkinci nümunədə, $14$ dadlılığı olan $6$ restoran nöqtəsi var:

1. $(2;5)$: $f(2,5)=(2\oplus 5)+(2|5)+(2\&5)=7+7+0=14;$

2. $(3;4)$: $f(3,4)=7+7+0=14;$

3. $(3;5)$: $f(3,5)=6+7+1=14;$

4. $(4;3)$: $f(4,3)=7+7+0=14;$

5. $(5;2)$: $f(5,2)=7+7+0=14;$

6. $(5;3)$: $f(5,3)=6+7+1=14.$

Göstərmək olar ki, verilmiş sərhədlərdə $14$-dən daha çox dadlılığa sahib restoran yoxdur.

Qiymətləndirmə

1. ($11$ bal): $n<2^{10}$;

2. ($19$ bal): $n=2^k-1$ , bəzi tam ədəd $k$ üçün $(1\le k\le 20)$;

3. ($14$ bal): $n<2^{20}$;

4. ($14$ bal): $n=2^k-1$ , bəzi tam ədəd $k$ üçün $(1\le k\le 60)$;

5. ($42$ bal): əlavə məhdudiyyət yoxdur.