牛客F-解方程(狄利克雷卷积)

package main

import (
    "bufio"
    "fmt"
    "os"
    "sync"
)

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a == min(a, b) {
        return b
    }
    return a
}
func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

var out chan string
var in *bufio.Scanner
var outWg *sync.WaitGroup

func GetNum(p string) int64 {
    var ans int64 = 0
    flag := true
    i := 0
    n := len(p)
    if p[i] == '-' {
        flag = false
        i++
    }
    for ; i < n; i++ {
        ans = (ans << 1) + (ans << 3) + int64(p[i]-'0')
    }
    if !flag {
        ans = -ans
    }
    return ans
}
func ReadString() string {
    in.Scan()
    return in.Text()
}
func ReadStringSlice(n int) []string {
    s := make([]string, n)
    for i := 0; i < n; i++ {
        s[i] = ReadString()
    }
    return s
}
func ReadInt() int {
    intStr := ReadString()
    return int(GetNum(intStr))
}
func ReadIntSlice(n int) []int {
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        arr[i] = ReadInt()
    }
    return arr
}
func ReadInt64() int64 {
    int64Str := ReadString()
    return GetNum(int64Str)
}
func ReadInt64Slice(n int) []int64 {
    arr := make([]int64, n)
    for i := 0; i < n; i++ {
        arr[i] = ReadInt64()
    }
    return arr
}

func init() {

    in = bufio.NewScanner(os.Stdin)
    in.Buffer(make([]byte, 1<<10), int(2e+5))
    in.Split(bufio.ScanWords)

    out = make(chan string, 1<<4)
    outWg = &sync.WaitGroup{}
    outWg.Add(1)
    writer := bufio.NewWriterSize(os.Stdout, int(2e+5))
    go func(write *bufio.Writer) {
        defer outWg.Done()
        defer write.Flush()
        for line := range out {
            write.WriteString(line + "\n")
        }
    }(writer)
}
func ksm(A,B,C int)int{
    var a,b,c int64 = int64(A),int64(B),int64(C)
    if b < 0 {
        b=-b
    }
    var ans int64 = 1
    for;b>0;b>>=1{
        if (b&1==1){
            ans=ans*a%c
        }
        a=a*a%c
    }
    return int(ans)
}
func mul(a,b,c int)int{

    return a*b%c
}
const (
    N = 1e7+5
    mod = 998244353
)
var n,p,q,cnt int
var f,Q,pri [N]int

var vis [N]bool
func work() {
    n,p,q = ReadInt(),ReadInt(),ReadInt()
    k := p-q
    Q[1],f[1]=1,1
    for i:=2;i<=n;i++{
        if !vis[i]{
            cnt++
            pri[cnt]=i
            Q[i]=ksm(i,q,mod)
            a := ksm(i,k,mod)
            if k < 0{
                a = ksm(a,mod-2,mod)
            }
            a = (mod+1-a)%mod
            f[i]=mul(Q[i],a,mod)
        }
        for j:=1;j<=cnt&&i*pri[j]<=n;j++{
            Q[i*pri[j]]=mul(Q[i],Q[pri[j]],mod)
            vis[i*pri[j]]=true
            if i%pri[j] == 0{
                f[i*pri[j]] = mul(f[i],Q[pri[j]],mod)
                break
            }
            f[i*pri[j]] = mul(f[i],f[pri[j]],mod)
        }
    }
    ans := 0
    for i:=1;i<=n;i++{
        ans ^= f[i]
    }
    fmt.Println(ans)
}

func main() {
    //for t := ReadInt(); t > 0; t-- {
        work()
    //}
    close(out)
}