Bins and balls#9557
ישנם פחים של ברצף. יש גם היצע אינסופי של כדורים בצבעים שונים של . מניחים בדיוק כדור אחד לכל פח, עם ההגבלה שפחים סמוכים אינם יכולים להכיל כדורים מאותו צבע. כמה תצורות חוקיות של כדורים בפחים יש.
מספר שלם אחד n~(1 \le n \le 10^9).
הדפס את מספר התצורות התקפות של כדורים בפחים mod 10^9 + 7.
Example 1