解説

包除原理を考えます

答えは

• $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)

xxxxxxxxxx

n,x,y=map(int,input().split())

mod=10**9+7

ans=(pow(y-x+1,n,mod)-2*pow(y-x,n,mod)+pow(y-x-1,n,mod))%mod

print(ans)