U116358 数论.练习储备八——一道♂题

​ 众所周知，ThinkofBlank是一个蒟蒻，这不，当他做这样一道题时: ​ $\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)==1]$ ​ 他竟然把式子推错了。。。尴尬症都犯了。。。

​ 他把式子推成了: ​ $\sum_{k=1}^{n}u[k]\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)==k]$ ​ ThinkofBlank:我到底是怎么做到的啊？！！！ ​ （其中,u[k]是莫比乌斯函数，至于真值表达式什么的，也不用我解释了吧？） ​ 异常愤怒的ThinkofBlank决定，把这个式子算出来！但由于他太弱了，于是他需要寻求你——史前巨佬的帮助！ ​ 由于式子的答案很大，你需要将答案对 18446744073709551616取模(wtf???)【负数的话请模成正数】

一个数，表示式子中的n

一个数，表示式子的答案

n