堡堡刚刚学会了数论中的原根。现在他正通过即时通信软件向小青鱼炫耀他的知识。
:::align{center}
本图仅为娱乐，与题目本身无关。如果您看不懂中文，可以安全地跳过本图。
:::
因为如果非负整数 是模 的原根（ 是质数），则 ，所以堡堡打算用表达式 来检查 是不是模 的原根。不幸的是，在大多数编程语言中（例如 C 和 C++）， 是按位异或（XOR）运算符，而不是次方运算符。小青鱼一下子就发现了这个错误，现在他开始思考起以下问题：
给定质数 和非负整数 ，有多少非负整数 满足 且 ？这里 是按位异或（XOR）运算符。
请帮助小青鱼解决这个问题。
