Vì kết quả có thể rất lớn nên chỉ cần in kết quả sau khi chia lấy dư cho $10^9+7$.