```go
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

const MOD int64 = 1000000007

func modpow(base, exp, mod int64) int64 {
	res := int64(1)
	base %= mod
	for exp > 0 {
		if exp%2 == 1 {
			res = (res * base) % mod
		}
		base = (base * base) % mod
		exp /= 2
	}
	return res
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var p, k int64
	fmt.Fscan(in, &p, &k)
	k %= p
	if k == 0 {
		fmt.Println(modpow(p, p-1, MOD))
		return
	}
	m := p - 1
	divs := []int64{}
	for i := int64(1); i*i <= m; i++ {
		if m%i == 0 {
			divs = append(divs, i)
			if i != m/i {
				divs = append(divs, m/i)
			}
		}
	}
	sort.Slice(divs, func(i, j int) bool { return divs[i] < divs[j] })
	var ord int64 = -1
	for _, d := range divs {
		if modpow(k, d, p) == 1 {
			ord = d
			break
		}
	}
	exp := (p - 1) / ord
	ways := modpow(p, exp, MOD)
	if k == 1 {
		ways = (ways * p) % MOD
	}
	fmt.Println(ways)
}
```