$%=1e9+7;$\+=(/ /+$`>>1)%$%*($'%$%),$\%=$%for<>;print