Alice lives on a farm, and one day she bought N sheep (she had not previously). Due to the reproduction of sheep, the number of sheep will double every D days. Since Alice does not want the number of sheep to be too large, she will sell half of the sheep she owns every R days (If it doubles and sells on the same day, then the sheep doubles first). But Alice is still worried that the number of sheep will be very large, so she wants you to tell her what the number of sheep will be after M days? In order to avoid an overly large answer, please output the result mod 1e9 + 7.