/^(.)+(?{($\+=$\+-$%!~($%=p^$1^$%||$%))%=1e9+7})^/+$%++for<>;print