注意到 Alice 赢、Bob 赢、平局的概率是相等的，因此答案就是 $$ 3^n\sum_{a,b}\gcd(a,b){n\choose a,b,n-a-b} $$ 由于 $n=\sum_{d\mid n}\varphi(d)$（或者莫比乌斯反演也可以得到同样的式子），可以改写成 $$ 3^n\sum_{1\le d\le n}\varphi(d)\sum_{d\mid a,d\mid b}{n\choose a,b,n-a-b} $$ 注意这里 $a=b=0$ 时会多算，需要减掉。

枚举 $d$，后面关于 $a$, $b$ 的部分就是一个卷积，卷积的长度是 $n/d$，可以直接 FFT。注意模数不是 $998\,244\,353$。

时间复杂度 $O(n\log ^2n)$。