解説

包除原理を考えます

答えは

• $X$から$Y$のいずれかの値をもつ長さ$N$の数列の通りを$P$通り
• $X-1$から$Y$のいずれかの値をもつ長さ$N$の数列を$Q$通り
• $X$から$Y-1$のいずれかの値をもつ長さ$N$の数列$R$通り
• $X-1$から$Y-1$のいずれかの値をもつ長さ$N$の数列$S$通り とすると$P-(Q+R)+S$となります。 冪乗は$N$の制約から繰り返し$2$乗をすると高速に求まリます。

実装例 (Python)